Wie Viele Primzahlen Gibt Es Bis 100
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 thousand�glich, per Siebverfahren in ziemlich kurzer Zeit alle 5484598 Primzahlen von 2 bis 94906249 zu bestimmen, mit denen alle nat�rlichen Zahlen bis two53-1=9007199254740991 per animate being-force-Teilbarkeitstests faktorisiert werden 1000�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 106er-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. Dice Zahl i 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�vii�67 ), was Primfaktorzerlegung (siehe unten) genannt wird. Geh�rte das neutrale Element der Multiplikation, die Zahl 1, zu den Primzahlen, then chiliad�lte diese Regel nicht.
P = {two, iii, 5, vii, 11, xiii, 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 northward�mlich stets das Produkt aus allen schon gefundenen Primzahlen bilden und one addieren. Keine der verwendeten Faktoren kann Teiler der then entstandenen Zahl sein, denn stets bleibt beim Teilen der Remainder 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 five.Chr.) beschrieb ein Verfahren zur Findung aller Primzahlen bis zur Grenze m, das heute als das Sieb des Eratosthenes bekannt ist. Homo streiche innerhalb der Liste der nat�rlichen Zahlen >ane und ≤m alle Vielfachen von 2, dann von der northward�chsten stehengebliebenen Zahl 3, dann wieder von der n�chsten noch nicht gestrichenen Zahl (5) usf. Es bleiben die Primzahlen stehen.
Will homo 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 t2≤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>√north, 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.)
Primfaktorzerlegung
Jede nat�rliche Zahl kann als ein bis auf die Reihenfolge eindeutiges Produkt von Primzahlen geschrieben werden. Dieses Produkt nennt human die Primfaktorzerlegung der Zahl. Beispiele:
700 = 2�2�5�five�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 dice zu zerlegende Zahl durch sie ohne Rest glatt teilbar ist. In diesem Autumn schreibt human being die Primzahl auf, teilt dice 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, besides: eine 2 gemerkt und 2394:ii=1197 berechnen. 1197 ist nicht mehr durch 2, aber durch three teilbar. 3 merken, Caliber: 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 vii teilbar. 7 merken; 133:7=nineteen. Das ist eine Primzahl, d.h. die Primfaktorzerlegung ist gefunden mit 2394=two�3�3�vii�xix oder 2�three2�7�19.
ggT und kgV
Der gr��te gemeinsame Teiler (ggT) zweier Zahlen ist das Produkt aus denjenigen Primzahlen, dice beide Primfaktorzerlegungen genau gemeinsam haben.
Bsp.: 53667 = iii�3�67�89 | 459486 = ii�three�3�three�67�127 | ggT(53667;459486)=three�3�67=603
Ohne Primfaktorzerlegung 50��t sich der ggT zweier Zahlen mit dem Euklidschen Algorithmus bestimmen.
Wenn f�r zwei Zahlen a und b gold: 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�three�iii�iii�67�89�127=40894254.
Es gilded 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 AlgorithmusBesondere Zahlen
Die Zahlen Grandgrand = 2k-1
(one thousand ∈ IN) hei�en Mersennesche Zahlen. Mk kann nur dann eine Primzahl sein, wenn k eine Primzahl ist. Man chapeau herausgefunden, da� es f�r k<20000 genau 24 Mersennesche Primzahlen gibt, n�mlich f�rthousand ∈ {2, 3, 5, 7, 13, 17, nineteen, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937}.219937-i ist eine Zahl mit 6002 Stellen (anschauen hier). Es sind sogar noch h�here Mersennesche Primzahlen bekannt, z.B.ii756839-i , eine Zahl mit 227.832 Stellen, oder die 1999 als Primzahl gefundenetwo6972593-one mit 2.098.960 Stellen, oder (im November 2003 entdeckt) die Mersennesche Zahltwo20996011-1 mit6320430 Stellen .
2018 wurde entdeckt, da�ii82589933-1 eine Primzahl ist, eine Zahl mit 24.862.048 Stellen.
Siehe f�r eine aktuelle �bersicht des GIMPS-Projekts (Nifty Internet Mersenne Prime Search): →mersenne.org.
Ob es unendlich viele dieser Primzahlen gibt, ist unbekannt.Dice Zahlen Fchiliad =
+1 mit
k ∈ IN hei�en Fermatsche Zahlen. Pierre de Fermat (1601-1665) vermutete, da� alle diese Zahlen Primzahlen seien. F�r one thousand∈{0, 1, two, 3, four} trifft das zu, f�r h�here thousand 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 + iii und28 = i + 2 + four + vii + 14 . Auf Pythagoras soll geht dice Erkenntnis zur�ckgehen, da� vollkommene Zahlen immer eine Summe aufeinanderfolgender Zahlen sind:28 = i + 2 + 3 + four + five + 6 + seven ,8128 = 1 + 2 + ... + 126 + 127. Euklid stellte fest, da� sich vollkommene Zahlen immer so darstellen lassen:2n-one�(twonorth-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 ist219936�(219937-1) eine Vollkommene Zahl.232582657-1�(232582657-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:
Human being 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 dice 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) grand�nnen gefunden werden �ber die Option "Teilersumme eintragen". Damit wird dice Teilersumme automatisch in das Eingabefeld �bernommen, so da� man nur noch wiederholt auf die Schaltfl�che klicken mu�, um dice Folge zu �berpr�fen. Beachte auch die Primfaktorzerlegung befreundeter Zahlenpaare! Gibt es eine Regel?
Die fifty�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 northwardp-1 stets um 1 gr��er als das due north�chst kleinere Vielfache von p (sogenannter Kleiner Satz von Fermat → Beweis).
Beispiele: a) ivv-1 = 44 = 25 6 , 25 5 = 5�51 b) thirteen17-1= 1316 = 66541660918317984 1 , 66541660918317984 0 = 39142153481363520�17 Jede Primzahl p, die sich durch p=4n+1 erzeugen l��t
(north ∈ IN) , l��t sich eindeutig als Summe von zwei ganzzahligen Quadraten darstellen (Bsp.: 233=eight2+132).Satz von Lagrange: Jede nat�rliche Zahl n 50��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 Grade
p = n�a + b (northward ∈ IN) .Dreiprimzahlsatz: Jede ungerade nat�rliche Zahl ≥9 ist Summe dreier ungerader Primzahlen. (Vergleiche mit der Goldbachschen Vermutung)
Vermutungen und offene Fragen
Primzahlzwillinge:Zwei Primzahlen, die in der Reihe der ungeraden Zahlen benachbart sind, nennt man Primzahlzwillinge, z.B.: iii 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, dice gleich der Summe ihrer echten Teiler au�er sich selbst, jedoch einschlie�lich der i, sind. (Siehe oben.) Es gibt sehr viele Zahlen, deren Teilersumme nur um i 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 dice rho-Methode
Den Primzahlen ist bis vor kurzer Zeit kein besonders hoher praktischer North�hrwert einger�umt worden. Doch seit der Entwicklung moderner Verschl�sselungsverfahren chapeau sich das entscheidend ge�ndert. Dice 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. Dice Sicherheit der Verschl�sselung besteht gerade darin, da� die Primfaktorzerlegung der Code-Zahlen unbekannt ist und auch aufgrund der Gr��east der Zahlen nur mit viel zu hohem Aufwand zu berechnen due west�re.
Beim sogenannte RSA-Verfahren wird ein
Schl�sselpaaraus zwei Zahlen east und northward ver�ffentlicht, wobei n ein Produkt aus zwei sehr gro�en Primzahlen p und q ist, und east eine Zahl, die keinen gemeinsamen Teiler mit (p-1)�(q-one) hat. Dieses Produkt ist �brigens die Menge aller Zahlen <n, die keinen gemeinsamen Teiler mit n au�er der ane haben. Mit der Formel10e mod due north → y werden die Zahlen verschl�sselt."modernistic n" bedeutet dabei, da� nur der Residue der Zahl 10eastward bei der Division durch n betrachtet wird. Dadurch geraten dice Ergebnisse sodurcheinander, da� ihnen nicht mehr anzusehen ist, wo sie herkommen. Auch, und das ist das Faszinierende, mit Kenntnis der Zahlen due north 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:
yd 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, likewise 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�due east Zahlen in �berschaubarer Zeit in ihre Primfaktoren zerlegen zu chiliad�nnen.Der erste Wunsch wird mehr oder weniger erf�llt durch ein Verfahren, das probabilistischer Primzahltest genannt wird.
Probareist das lateinische Wort f�r probieren, testen, versuchen. Dice zu testende zahl, ein k�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, due north�mlich(one/iv)100 ~6,223�10-59%. Der Proper 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 chiliad�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�
two32+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 ap-1 durch p der Rest 1 bleibt, wenn p eine Primzahl ist und a kein Vielfaches von p, der Schl�ssel zu allen Chiliad�glichkeiten liegt, das schnell herauszufinden. (Vergleiche oben → Mersennesche Zahlen.)Noch vor knapp 150 Jahren hielt der englische �konom W. Southward. Jevons es f�r absolut unwahrscheinlich, da� irgendjemand jemals herausfinden west�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 Coffee-Applet zur Verf�gung gestellt werden, mu� Java aktiviert sein. Ich habe mich f�r die Coffee-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-Fleck-Zahlen oder auch fifteen 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 The states verbot bis vor kurzer Zeit (Stand 2002) den
Exportvon Browsern mit Programm-Modulen, die mit gr��eren Schl�sseln als forty Flake 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 thousand�glich. Wer die Primfaktoren des Schl�ssels kennt, kann dice 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 human aus der Primfaktorzerlegung des �ffentlichen Schl�ssels berechnen.
Dice 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, Thought, 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 dice Primzahlen nicht, mit der es den Schl�ssel generiert hat, sondern beginnt die Suche immer treudoof aus dem Nichts.)
Offensichtlich haben 40bit-RSA-Schl�ssel dice Geheimhaltungsf�higkeit einer mit Sch�nschrift beschriebenen Ansichtskarte, bei 64 Flake ist es dann vielleicht eine Handschrift wie meine. Und bei 128bit-Schl�sseln...? Das Coffee-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 Connected Fraction = unendliche Kettenbr�che. Dice 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 human 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 dice 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 two und
fourteen Minuten). Java, die Sprache des Programms hinter dieser Seite, ist gegen Maschinenprogramme oder auch C++-Programme immer noch ziemlich langsam. Legen Sie dice maximale Zeit fest, dice 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.ii. Dies faktorisierte alle getesteten 128-Flake-Schl�ssel auf meinem Laptop in sage und schreibe, festhalten!, nur
iv Sekunden. (Wie ist das one thousand�glich?!)Die �bermittlung der symmetrischen Schl�ssel erfolgt heute mit RSA-Schl�sseln mit 1924 Chip. Bislang ist keine mathematische Methode bekannt, solche Zahlen innerhalb einer Lebensspanne zu faktorisieren. Aber wer wei�: Vielleicht gibt es schon Maschinen, dice mit geheimen mathematischen Methoden auch gro�due east Schl�ssel in Minuten- oder zumindest Tagesfrist knacken!
Version: 7. six. 2021
© Arndt Br�nner
Matheseiten�berblick
zurück
Das GIMPS-Projekt
Gr��te z.Z. bekannte Primzahl (7816230 Stellen)
Source: https://www.arndt-bruenner.de/mathe/scripts/primzahlen.htm
0 Response to "Wie Viele Primzahlen Gibt Es Bis 100"
Post a Comment