Matheseitenüberblick   •  Pythagoreische Tripel   •  zurück   •  © Arndt Brünner

Die Primzahlseite

       ...funktioniert nur, wenn Javascript aktiviert ist.

Hinweis: Ich habe Anfang Juni 2021, weil diese sehr alte Seite dem Anschein nach immer noch recht häufig frequentiert wird, die Primzahlberechnung und Faktorisierung ganz auf Javascript umgestellt und sehr viel schneller gemacht. Die heutige Leistung der Browser macht es möglich, per Siebverfahren in ziemlich kurzer Zeit alle 5484598 Primzahlen von 2 bis 94906249 zu bestimmen, mit denen alle natürlichen Zahlen bis 2⁵³-1=9007199254740991 per brute-force-Teilbarkeitstests faktorisiert werden können, d.h. alle in Javascript genau (sicher) darstellbaren Zahlen. Initial werden die Primzahlen bis 9999991 berechnet (Zeitaufwand dafür (hier soeben im Browser): ). Wenn das hinreichend schnell ging, sonst beim ersten Bedarf, wird die Liste bis zur erwähnten Grenze erweitert − dann eventuell noch (für Goldbach) in 10⁶er-Schritten auch weiter − und steht dann zur Verfügung.

Erläuterungen: Primzahlen  •   Primfaktorzerlegung  •   ggT und kgV  •   besondere Zahlen  •   Primzahlsätze  •   Vermutungen, Fragen  •   Verwendung von großen Primzahlen in sicheren Verschlüsselungsverfahren

Erläuterungen: Primzahlen  •   ggT und kgV  •   besondere Zahlen  •   Primzahlsätze  •   Vermutungen, Fragen

 

Primzahlen

... sind natürliche Zahlen, die nur durch sich selbst und 1 (ohne Rest) teilbar sind. Die Zahl 1 erfüllt zwar diese Bedingung, gehört jedoch nicht zur Menge der Primzahlen. Jede natürliche Zahl n>1 kann (bis auf die Reihenfolge) eindeutig als Produkt von Primzahlen dargestellt werden. (Bsp.: 2345 = 5·7·67), was Primfaktorzerlegung (siehe unten) genannt wird. Gehörte das neutrale Element der Multiplikation, die Zahl 1, zu den Primzahlen, so gälte diese Regel nicht.
P = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199 ...}

Es gibt unendlich viele Primzahlen. Man kann nämlich stets das Produkt aus allen schon gefundenen Primzahlen bilden und 1 addieren. Keine der verwendeten Faktoren kann Teiler der so entstandenen Zahl sein, denn stets bleibt beim Teilen der Rest 1. Das heißt: Diese Zahl muß eine bislang unbekannte Primzahl als Teiler besitzen! So läßt sich stets eine weitere Primzahl finden, egal wie viele schon bekannt sind.

Der griechische Mathematiker Eratosthenes (ca. 275 - 194 v.Chr.) beschrieb ein Verfahren zur Findung aller Primzahlen bis zur Grenze m, das heute als das Sieb des Eratosthenes bekannt ist. Man streiche innerhalb der Liste der natürlichen Zahlen >1 und ≤m alle Vielfachen von 2, dann von der nächsten stehengebliebenen Zahl 3, dann wieder von der nächsten noch nicht gestrichenen Zahl (5) usf. Es bleiben die Primzahlen stehen.

Will man prüfen, ob eine Zahl n eine Primzahl ist, so genügt es, mögliche Teiler t der Zahl nur für alle t mit t²≤n zu suchen, also t≤√n, denn größere t können keine Teiler von n mehr sein, wenn keine kleineren Teiler existieren. Wenn t>√n, dann ist t·t>n. Beim Testen, ob die Zahl 5987 eine Primzahl ist, muß also nur für die Primzahlen bis √5987, also bis 73 geprüft werden, ob sie 5987 teilen. Wenn sich bis da keine Primzahl findet, die Teiler von 5987 ist, ist 5987 eine Primzahl. (Sie ist es.)

Die Verteilung der Primzahlen ist unregelmäßig. Sie treten bei hohen Zahlen immer seltener auf.
Für die Anzahl der Primzahlen ≤x fand Gauß eine Näherungsformel: Sie nähert sich demnach bei wachsendem x dem Wert x/ln(x) an.
 

Ausprobieren: bis zu x = gibt es etwa Primzahlen.

 

Primfaktorzerlegung

Jede natürliche Zahl kann als ein bis auf die Reihenfolge eindeutiges Produkt von Primzahlen geschrieben werden. Dieses Produkt nennt man die Primfaktorzerlegung der Zahl. Beispiele: 700 = 2·2·5·5·7;  562309 = 11·17·97·31. Es gibt jeweils keine andere Möglichkeit, mit anderen als mit diesen Faktoren auf dieses Produkt zu kommen, wenn alle Faktoren Primzahlen sein sollen. Weitere Beispiele beliebiger Zahl über das obige Formular.

Zur Gewinnung der Primfaktorzerlegung geht man gewöhnlich die Primzahlen von unten (d.h. 2, 3, 5, 7...) durch und prüft, ob die zu zerlegende Zahl durch sie ohne Rest glatt teilbar ist. In diesem Fall schreibt man die Primzahl auf, teilt die zu zerlegende Zahl durch die Primzahl und macht mit dem Ergebnis (dem Quotienten) weiter, bis am Schluß nur noch eine Primzahl übrig bleibt.

Beispiel: 2394 soll in Primfaktoren zerlegt werden. 2394 ist durch 2 teilbar, also: eine 2 gemerkt und 2394:2=1197 berechnen. 1197 ist nicht mehr durch 2, aber durch 3 teilbar. 3 merken, Quotient: 1197:3=399. 399 ist nochmal durch 3 teilbar: die zweite 3 merken, Quotient: 133. Das ist nicht mehr durch 3 und nicht durch 5, aber durch die 7 teilbar. 7 merken; 133:7=19. Das ist eine Primzahl, d.h. die Primfaktorzerlegung ist gefunden mit 2394=2·3·3·7·19 oder 2·3²·7·19.

 

ggT und kgV

Der größte gemeinsame Teiler (ggT) zweier Zahlen ist das Produkt aus denjenigen Primzahlen, die beide Primfaktorzerlegungen genau gemeinsam haben.
Bsp.: 53667 = 3·3·67·89 | 459486 = 2·3·3·3·67·127 | ggT(53667;459486)=3·3·67=603
Ohne Primfaktorzerlegung läßt sich der ggT zweier Zahlen mit dem Euklidschen Algorithmus bestimmen.
Wenn für zwei Zahlen a und b gilt: ggT(a;b)=1, dann haben a und b keinen gemeinsamen Teiler. Sie heißen daher auch teilerfremd.

Das kleinste gemeinsame Vielfache (kgV) zweier Zahlen ist das Produkt aus allen Primzahlen, die in den Primfaktorzerlegungen der beiden Zahlen vorkommen, und zwar in der höchsten vorkommenden Potenz. Bsp.: kgV(53667;459486)=2·3·3·3·67·89·127=40894254.
Es gilt ggT(a;b)·kgV(a;b)=a·b und somit kgV(a;b)=a·b/ggT(a;b).

→ Neue interaktive Seite zum Thema: Wie findet man den ggT?
→ alte Seite zum Euklidschen Algorithmus

 

Besondere Zahlen

Die Zahlen M_k = 2^k-1 (k ∈ IN) heißen Mersennesche Zahlen. M_k kann nur dann eine Primzahl sein, wenn k eine Primzahl ist. Man hat herausgefunden, daß es für k<20000 genau 24 Mersennesche Primzahlen gibt, nämlich für k ∈ {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937}. 2¹⁹⁹³⁷-1 ist eine Zahl mit 6002 Stellen (anschauen hier). Es sind sogar noch höhere Mersennesche Primzahlen bekannt, z.B. 2⁷⁵⁶⁸³⁹-1, eine Zahl mit 227.832 Stellen, oder die 1999 als Primzahl gefundene 2^6972593-1 mit 2.098.960 Stellen, oder (im November 2003 entdeckt) die Mersennesche Zahl 2^20996011-1 mit 6320430 Stellen.
2018 wurde entdeckt, daß 2^82589933-1 eine Primzahl ist, eine Zahl mit 24.862.048 Stellen.
Siehe für eine aktuelle Übersicht des GIMPS-Projekts (Great Internet Mersenne Prime Search): →mersenne.org.
Ob es unendlich viele dieser Primzahlen gibt, ist unbekannt.

Die Zahlen F_k = +1 mit k ∈ IN heißen Fermatsche Zahlen. Pierre de Fermat (1601-1665) vermutete, daß alle diese Zahlen Primzahlen seien. Für k∈{0, 1, 2, 3, 4} trifft das zu, für höhere k jedoch offensichtlich nicht – bislang wurde keine gefunden. Aber auch die Nichtexistenz einer solchen Zahl wurde noch nicht bewiesen.

„Vollkommene Zahlen“ nennt man Zahlen, die gleich der Summe ihrer echten Teiler außer sich selbst, aber einschließlich der 1 sind:
{6, 28, 496, 8128, 33550336, 8589869056, ...}. 6 = 1 + 2 + 3  und  28 = 1 + 2 + 4 + 7 + 14. Auf Pythagoras soll geht die Erkenntnis zurückgehen, daß vollkommene Zahlen immer eine Summe aufeinanderfolgender Zahlen sind: 28 = 1 + 2 + 3 + 4 + 5 + 6 + 7, 8128 = 1 + 2 + ... + 126 + 127. Euklid stellte fest, daß sich vollkommene Zahlen immer so darstellen lassen: 2^n-1·(2ⁿ-1), wobei n eine natürliche Zahl ist. Umgekehrt ergibt diese Formel immer genau dann eine vollkommene Zahl, falls n eine Mersennesche Primzahl ist. Zum Beispiel ist 2¹⁹⁹³⁶·(2¹⁹⁹³⁷-1) eine Vollkommene Zahl. 2^32582657-1·(2^32582657-1) ist die größte bekannte Vollkommene Zahl.

„Befreundete Zahlen“ sind zwei Zahlen, deren Teilersumme gleich der anderen Zahl ist. Sie wurden von Pierre Fermat untersucht und beschrieben, waren jedoch schon vorher bekannt. 220 und 284 sind befreundete Zahlen, 1184 und 1210; 17296 und 18416 sowie 9363584 und 9437056.
→ Liste aller bekannter befreundeter Zahlen (sortiert nach Stellenzahl) - externe Seite

Ausprobieren: Man kann im Formular oben prüfen, ob eine Zahl vollkommen ist, und zwar im Bereich Primfaktorzerlegung. Trage die Zahl in das Eingabefeld ein und aktiviere die Option "Teilermenge bestimmen". Dann wird nicht nur die Menge der Teiler berechnet, sondern auch die Teilersumme, die mit der eigegebenen Zahl verglichen werden kann. Befreundete Zahlen oder auch sogenannte "gesellige Zahlen", die eine geschlossene Kette bilden (z.B. 1264460-1547860-1727636-1305184-1264460) können gefunden werden über die Option "Teilersumme eintragen". Damit wird die Teilersumme automatisch in das Eingabefeld übernommen, so daß man nur noch wiederholt auf die Schaltfläche klicken muß, um die Folge zu überprüfen. Beachte auch die Primfaktorzerlegung befreundeter Zahlenpaare! Gibt es eine Regel? Die längste bekannte Kette geselliger Zahlen besteht aus 28 Zahlen und beginnt mit 14316. Ausprobieren und dann eine noch längere finden!

 

Sätze über Primzahlen

Sätze von Fermat:
Wenn p eine Primzahl ist und n eine Natürliche Zahl, die kein Vielfaches von p ist, dann ist n^p-1 stets um 1 größer als das nächst kleinere Vielfache von p (sogenannter Kleiner Satz von Fermat → Beweis).

Beispiele:	a)	45-1 = 44 = 256, 255 = 5·51
	b)	1317-1= 1316 = 665416609183179841, 665416609183179840 = 39142153481363520·17

Jede Primzahl p, die sich durch p=4n+1 erzeugen läßt (n ∈ IN), läßt sich eindeutig als Summe von zwei ganzzahligen Quadraten darstellen (Bsp.: 233=8²+13²).

Satz von Lagrange: Jede natürliche Zahl n läßt sich als Summe von höchstens vier Quadraten ganzer Zahlen darstellen.

Satz von Dirichlet: Wenn ggT(a,b)=1, dann gibt es unendlich viele Primzahlen p der Form p = n·a + b (n ∈ IN).

Dreiprimzahlsatz: Jede ungerade natürliche Zahl ≥9 ist Summe dreier ungerader Primzahlen. (Vergleiche mit der Goldbachschen Vermutung)

 

Vermutungen und offene Fragen

Die Goldbachsche Vermutung besagt, daß man jede gerade Zahl >2 als Summe zweier Primzahlen darstellen kann. Diese Vermutung erweist sich zwar als richtig für Zahlen bis weit über 100.000.000, konnte bislang aber weder für alle Zahlen bewiesen noch durch ein Gegenbeispiel widerlegt werden.

Christian Goldbach war 1742 Lehrer des russischen Zaren Peter II. Er teilte seine Entdeckung in einem Brief Leonhard Euler mit und bat ihn, zu beweisen, daß dies für alle Zahlen so sei. Trotz jahrelanger Bemühung gelang Euler kein Beweis.
 

Ausprobieren: gerade Zahl eingeben: Vorsicht! Bei großen Zahlen müssen unter Umständen zunächst sehr viele Primzahlen berechnet werden, was recht lange dauern kann. In der Statusleiste des Browsers (falls aktiviert) ist zu sehen, wie das Programm sucht bzw. was es tut.

Primzahlzwillinge:Zwei Primzahlen, die in der Reihe der ungeraden Zahlen benachbart sind, nennt man Primzahlzwillinge, z.B.: 3 und 5; 17 und 19 oder 10007 und 10009. Es ist noch ungeklärt, ob es unendlich viele Primzahlzwillinge gibt.

Vollkommene Zahlen nennt man Zahlen, die gleich der Summe ihrer echten Teiler außer sich selbst, jedoch einschließlich der 1, sind. (Siehe oben.) Es gibt sehr viele Zahlen, deren Teilersumme nur um 1 kleiner ist als die Zahl, z.B. alle Potenzen der 2; jedoch ist noch keine Zahl gefunden worden, deren Teilersumme um 1 oder auch nur wenig größer ist als die Zahl selbst. Es ist auch bislang unbewiesen, ob es solche Zahlen überhaupt geben kann. Vor allem ist es bis heute nicht klar, ob es auch ungerade vollkommene Zahlen gibt.

 

Es gibt noch viele andere ungelöste Probleme über Primzahlen! Demnächst mehr davon.

Der probabilisitische Primzahltest und die rho-Methode

Den Primzahlen ist bis vor kurzer Zeit kein besonders hoher praktischer Nährwert eingeräumt worden. Doch seit der Entwicklung moderner Verschlüsselungsverfahren hat sich das entscheidend geändert. Die meisten heutigen Verfahren, auch das Sicherheitsprotokoll bei sogenannten sicheren Internetverbindungen (z.B. beim Homebanking), benötigen Zahlen, die nur wenige, jedoch sehr große Primfaktoren besitzen. Die Sicherheit der Verschlüsselung besteht gerade darin, daß die Primfaktorzerlegung der Code-Zahlen unbekannt ist und auch aufgrund der Größe der Zahlen nur mit viel zu hohem Aufwand zu berechnen wäre.

Beim sogenannte RSA-Verfahren wird ein Schlüsselpaar aus zwei Zahlen e und n veröffentlicht, wobei n ein Produkt aus zwei sehr großen Primzahlen p und q ist, und e eine Zahl, die keinen gemeinsamen Teiler mit (p-1)·(q-1) hat. Dieses Produkt ist übrigens die Menge aller Zahlen <n, die keinen gemeinsamen Teiler mit n außer der 1 haben. Mit der Formel x^e mod n → y werden die Zahlen verschlüsselt. "mod n" bedeutet dabei, daß nur der Rest der Zahl x^e bei der Division durch n betrachtet wird. Dadurch geraten die Ergebnisse so durcheinander, daß ihnen nicht mehr anzusehen ist, wo sie herkommen. Auch, und das ist das Faszinierende, mit Kenntnis der Zahlen n und e ist das Verfahren nicht mehr rückgängig zu machen!

Daher können diese beiden Zahlen auch veröffentlicht werden − sie dienen der Verschlüsselung von Nachrichten für den Besitzer des Schlüsselpaares. Dieser kennt als einziger die beiden Primzahlen p und q, mit denen er eine Zahl d berechnen kann, die verschlüsselte Zahlen wieder entschlüsseln kann: y^d mod (p-1)(q-1) → x .

Sichere Internetverbindungen funktionieren in der Regel an entscheidender Stelle nach diesem System. Zunächst wird von jeder Seite ein Schlüssel übermittelt, mit dem das Gegenüber einen Schlüssel zur konventionellen Verschlüsselung zurücküberträgt. Konventionelle (symmetrische) Verschlüsselung ist wesentlich schneller − und außerdem ist die RSA-Verschlüsselung dann noch sicherer, wenn nur wenige Informationen, also lediglich der symmetrische Schlüssel − mit einem RSA-Schlüssel übertragen werden.

Einerseits besteht daher nun Bedarf an sehr großen Primzahlen zur sicheren Verschlüsselung von Informationen, andererseits (auf der Gegenseite, nämlich bei denen, die Geheimnisse entschlüsseln wollen) der Wunsch nach effektiven Verfahren, sehr große Zahlen in überschaubarer Zeit in ihre Primfaktoren zerlegen zu können.

Der erste Wunsch wird mehr oder weniger erfüllt durch ein Verfahren, das probabilistischer Primzahltest genannt wird. Probare ist das lateinische Wort für probieren, testen, versuchen. Die zu testende zahl, ein möglicher Primzahlkandidat, durchläuft ein spezielles mathematischen Verfahren (demnächst erscheint hier eine spezielle Seite darüber), bei dem sehr rasch entschieden werden kann, ob es sich definitiv um keine Primzahl handelt oder mit 75%-iger Wahrscheinlichkeit eine Primzahl ist. Wenn der Test unter bestimmten Bedingungen hundertmal durchlaufen wird, so ist demnach seine Fehlerquote extrem gering, nämlich (1/4)¹⁰⁰ ~ 6,223·10^-59%.

Der Name der rho-Methode leitet sich vom griechischen Buchstaben ρ ab. Diesen verlieh ihr ihr Entwickler John Michael Pollard, weil im Verfahren gelegentlich periodische Folgen auftreten. Das Verfahren selbst faktorisiert vor allem große Zahlen mit recht großer Sicherheit (aber auch mit möglichem Fehler, über deren Wahrscheinlichkeit bislang noch keine zahlenmäßige Aussage gemacht werden kann) in hoher Geschwindigkeit.

Im Jahre 1640 schrieb Fermat an Mersenne, er vermute, daß 2³²+1 = 4294967297 eine Primzahl sei, könne es aber nicht definitiv beweisen. Weder er noch Mersenne lösten das Problem, obgleich gerade in Fermats Erkenntnis, daß beim Teilen jeder Zahl a^p-1 durch p der Rest 1 bleibt, wenn p eine Primzahl ist und a kein Vielfaches von p, der Schlüssel zu allen Möglichkeiten liegt, das schnell herauszufinden. (Vergleiche oben → Mersennesche Zahlen.)

Noch vor knapp 150 Jahren hielt der englische Ökonom W. S. Jevons es für absolut unwahrscheinlich, daß irgendjemand jemals herausfinden würde, welche beiden Zahlen er multipliziert habe, um 8616460799 zu erhalten. Selbst das Javascript hinter dieser Seite bekommt es in Millisekunden heraus.

Da auf dieser Seite beide Verfahren über ein Java-Applet zur Verfügung gestellt werden, muß Java aktiviert sein. Ich habe mich für die Java-Lösung entschieden wegen der enormen Geschwindigkeitsvorteile und aufgrund der Tatsache, daß das Applet theoretisch mit beliebig großen Zahlen hantieren kann; auch praktisch weit über die Limits von 32-Bit-Zahlen oder auch 15 Stellen hinaus. Selbst mein derzeit langsamster Rechner (Pentium I, 100MHz, 32MB RAM, auf dem aber alle diese Seiten entstanden) faktorisiert das 55-stellige Produkt aus den jeweils größten ein-, zwei-, drei- bis zehnstelligen Primzahlen (7 · 97 · 997 · 9973 · 99991 · 999983 · 9999991 · 99999989 · 999999937 · 9999999967 = 6750622348964143051956305469326962117763788889781985387) in durchschnittlich 17 Sekunden (und mein derzeit schnellster in 2).

Sicheres Homebanking mit 128 Bit?

Eine Anmerkung zur Sicherheit von sicheren Internetverbindungen. Die USA verbot bis vor kurzer Zeit (Stand 2002) den Export von Browsern mit Programm-Modulen, die mit größeren Schlüsseln als 40 Bit ver- und entschlüsseln konnten. Heute sind Schlüssel mit 128 Bit üblich (und dürfen exportiert werden).

Handelte es sich dabei um RSA-Schlüssel, so wäre es um die Geheimhaltung nicht besonders gut bestellt, wie man unten auf dieser Seite lesen bzw. ausprobieren kann, denn dort ist die Faktorisierung solcher Zahlen über ein Applet in recht kurzer Zeit möglich. Wer die Primfaktoren des Schlüssels kennt, kann die mit ihm codierten Botschaften decodieren (siehe oben).

Die Schlüssel selbst sind ja öffentlich bekannt, das Geheimnis besteht nur in ihrer Primfaktorzerlegung. Das bedeutet: Wer den Schlüssel in seine Primfaktoren zerlegen kann, kann die verschlüsselte Nachricht entschlüsseln, weil er den Schlüssel zum Entschlüsseln berechnen kann! Wegen dieser Verschiedenheit der Schlüssel zum Ver- bzw. Entschlüsseln heißen solche Verfahren auch asymmetrisch.

Bei symmetrischen Verfahren verwenden Ver- und Entschlüsselung denselben Schlüssel. Dieser Schlüssel muß geheim bleiben. Der Vorteil des asymmetrischen Verfahren liegt darin, daß der Schlüssel zum Verschlüsseln öffentlich bekannt sein kann (ja muß), wohingegen nur der passende Gegenschlüssel (zum Entschlüsseln) geheimgehalten werden muß. Den passenden Gegenschlüssel kann man aus der Primfaktorzerlegung des öffentlichen Schlüssels berechnen.

Die eigentlichen RSA-Schlüssel bei sicheren Internetverbindungen nach RSA haben heute jedoch 1924 Bit und sind mit den derzeit bekannten Verfahren nicht in absehbarer Zeit zu faktorisieren.

Ein sicherer Datenaustausch kann nach diesem Muster funktionieren: Sollen geheime Daten von A nach B übermittelt werden, so schickt B zunächst seinen öffentlichen RSA-Schlüssel an A. Dieser codiert seinen symmetrischen Schlüssel nach RSA mit dem erhaltenen RSA-Schlüssel und schickt ihn codiert an B, welcher ihn mit seinem geheimen Schlüssel decodieren kann. Jetzt codiert A seine Botschaft symmetrisch und sendet sie an B. Da dieser jetzt über den symmetrischen Schlüssel verfügt, kann er die Botschaft entschlüsseln.
Heute sind im Internet symmetrische 128-Bit-Verschlüsselungen (Verfahren DES, 3DES, AES, Blowfisch, IDEA, CAST, u.a.) üblich, die auch von den neueren Exportversionen der Browser unterstützt werden.

Faktorisierung großer Zahlen

Wie sicher sind nun diese Schlüssel? Probieren Sie es aus: Erzeugen Sie hier eine Zahl, die nur zwei zufällige Primfaktoren besitzt (gefunden mit dem probabilistischen Testverfahren), und lassen Sie dann nach der Primfaktorzerlegung suchen. (Das Programm merkt sich die Primzahlen nicht, mit der es den Schlüssel generiert hat, sondern beginnt die Suche immer treudoof aus dem Nichts.)

	Schlüsselgröße: 40 Bit 64 Bit128 Bit1024 Bit 1924 Bit 2048 Bit4096 Bitanderewählen...
Zahl / Schlüssel:
	maximale Zeit: Sekunden
Primfaktoren:
	Algorithmus: rho-Methode (Pollard)CF-Methode (Morrison-Brillhardt) QF-Methode (Shanks)nach Carl Friedrich Gauß         benötigte Zeit:

Offensichtlich haben 40bit-RSA-Schlüssel die Geheimhaltungsfähigkeit einer mit Schönschrift beschriebenen Ansichtskarte, bei 64 Bit ist es dann vielleicht eine Handschrift wie meine. Und bei 128bit-Schlüsseln...? Das Java-Applet dieser Seite tut sich da schon schwer. Auf meinem schnellsten Rechner klappt es mit dem CF-Algorithmus von Morrison und Brillhardt immerhin im Durchschnitt in gut einer halben Stunde.

CF steht für Continued Fraction = unendliche Kettenbrüche. Die Entwicklung der Quadratwurzel der zu faktorisierenden Zahl in einen (nicht abbrechenden) Kettenbruch - siehe meine Seite dazu - und die sich daraus ergebenden Näherungsbrüche erzeugen Zahlen, mit denen man den verborgenen Faktoren - allerdings mit ziemlichem Rechenaufwand - auf die Schliche kommen kann. QF steht für quadratische Formen; auch dieser Algorithmus basiert auf der Kettenbruchzerlegung von √N. Die Geschwindigkeit der beiden Kettenbruch-Algorithmen hängt nach meinen Erfahrungen nicht nur von der Taktfrequenz des Prozessors, sondern ziemlich stark vom verfügbaren Speicherplatz des Rechners ab. Natürlich ist das Rechnen mit sehr großen Ganzzahlen grundsätzlich sehr speicherintensiv; jedoch ist der rho-Algorithmus bei weitem nicht so von diesem Aspekt abhängig. Der CF-Algorithmus ist übrigens bei kleinen Zahlen nicht wesentlich schneller als bei großen. Er empfiehlt sich also nur zur Faktorisierung sehr großer Zahlen, bei denen das rho-Verfahren die Segel streicht. Allerdings wird die Zahl bei den beiden Kettenbruch-Algorithmen zunächst probeweise durch die ersten 10000 Primzahlen (bis 104729) dividiert. Sind also alle Primfaktoren bis auf einen in diesem Bereich, so sind wiederum diese beiden im Vorteil - jedoch nur aufgrund der vorgeschalteten Probedivision.
Sehr interessant ist der (Geschwindigkeits-)Vergleich mit dem über 200 Jahre alten Algorithmus, den Carl Friedrich Gauß zum schriftlichen Faktorisieren großer Zahlen verwendete. Er entdeckte ihn vermutlich unabhängig von Euler, der einige Jahrzehnte vorher schon einen ähnlichen Algorithmus hatte. Natürlich gehen die modernen Algorithmen auf Gauß' und Eulers Ideen zurück. Verstecken muß sich das alte Verfahren jedenfalls ganz sicher nicht!

Ein halbwegs leistungsfähiges Mathematikprogramm, wie Derive, schafft die Faktorisierung eines 128-Bit-Schlüssels in einigen Minuten. Die Dauer ist – wie man auch hier feststellen kann – variabel und hängt in unvorhersehbarer Weise von der Zahl selbst ab. (Mit Derive variierte sie bei nicht allzuvielen Versuchen zwischen 2 und 14 Minuten). Java, die Sprache des Programms hinter dieser Seite, ist gegen Maschinenprogramme oder auch C++-Programme immer noch ziemlich langsam. Legen Sie die maximale Zeit fest, die Sie warten wollen.

Nachtrag: Ich vermutete ja, daß das "halbwegs leistungsfähige" Programm Derive, so gute Dienste es mir bislang ja erwies und so gerne ich damit arbeite, noch zu toppen ist, aber daß es solch ein Unterschied wird, hatte ich wirklich nicht erwartet: Nachdem ich dies geschrieben hatte, bekam ich die Mathematica-Version 4.2. Dies faktorisierte alle getesteten 128-Bit-Schlüssel auf meinem Laptop in sage und schreibe, festhalten!, nur 4 Sekunden. (Wie ist das möglich?!)

Die Übermittlung der symmetrischen Schlüssel erfolgt heute mit RSA-Schlüsseln mit 1924 Bit. Bislang ist keine mathematische Methode bekannt, solche Zahlen innerhalb einer Lebensspanne zu faktorisieren. Aber wer weiß: Vielleicht gibt es schon Maschinen, die mit geheimen mathematischen Methoden auch große Schlüssel in Minuten- oder zumindest Tagesfrist knacken!

Version: 7. 6. 2021
 
© Arndt Brünner
Matheseitenüberblick
zurück
 
Das GIMPS-Projekt
Größte z.Z. bekannte Primzahl (7816230  Stellen)