Möglichst große Primzahlen generieren

**ice.icewing**

Es sind (sehr wahrscheinlich) alle Primzahl bis weit in den Milliardenbereich hinein bekannt.
Eine neue noch unbekannte Primzahl zu finden dürfte mit einem einzelnen Computer unmöglich sein. Und die bekannten sind in irgendwelchen Listen verfügbar. Die vermutlich einfachste Lösung wäre also eine Liste von Primzahlen zu nehmen und daraus "zufällig" eine auszuwählen.
Hier ist eine Liste von "kleinen" Primtzahlen:

http://www.abide.de/docs/primzahlen.html

Um eine Zahl darauf zu Prüfen ob sie eine Primzahl ist gilt das Rabin Miller Verfahren als schnell und zuverlässig, auch wenn eine damit gefundene Zahl nicht mit 100%iger Sicherheit eine Primzahl ist. Dieses Verfahren kann man dann in einer Schleife auf Zahlen Anwenden, aber bei Zahlen über 2Mrd braucht man dann einen 128Bit Integer wenn ich mich recht erinnere.

**moritz**

Kurze Theorie zu den Primzahlen:
Primzahlen unterteilen sich in zwei Gruppen: Solche, die sich als 4n+1, und solche, die sich als 4n-1 darstellen lassen. Das ist schonmal eine Eigenschaft, mit der man die Anzahl der zu prüfenden Zahlen schonmal drastisch reduzieren kann.

Gruß

**Binärbaum**

Zitat von moritz:

Kurze Theorie zu den Primzahlen:
Primzahlen unterteilen sich in zwei Gruppen: Solche, die sich als 4n+1, und solche, die sich als 4n-1 darstellen lassen. Das ist schonmal eine Eigenschaft, mit der man die Anzahl der zu prüfenden Zahlen schonmal drastisch reduzieren kann.

Kommt das nicht auf das selbe raus wie 2n+1?
Das heißt dann ja, dass alle Primzahlen ungerade sind (bis auf die 2), und das ist ja auch nichts Neues.

MfG
Binärbaum

**moritz**

Zitat von Binärbaum:

Zitat von moritz:

Kurze Theorie zu den Primzahlen:
Primzahlen unterteilen sich in zwei Gruppen: Solche, die sich als 4n+1, und solche, die sich als 4n-1 darstellen lassen. Das ist schonmal eine Eigenschaft, mit der man die Anzahl der zu prüfenden Zahlen schonmal drastisch reduzieren kann.

Kommt das nicht auf das selbe raus wie 2n+1?
Das heißt dann ja, dass alle Primzahlen ungerade sind (bis auf die 2), und das ist ja auch nichts Neues.

MfG
Binärbaum

Nein. Durch 4n+1 btzw 4n-1 erreichst du weniger Zahlen und dadurch eine höhere Geschwindigkeit.

**Binärbaum**

Zitat von moritz:

Zitat von Binärbaum:

Zitat von moritz:

Kurze Theorie zu den Primzahlen:
Primzahlen unterteilen sich in zwei Gruppen: Solche, die sich als 4n+1, und solche, die sich als 4n-1 darstellen lassen. Das ist schonmal eine Eigenschaft, mit der man die Anzahl der zu prüfenden Zahlen schonmal drastisch reduzieren kann.

Kommt das nicht auf das selbe raus wie 2n+1?
Das heißt dann ja, dass alle Primzahlen ungerade sind (bis auf die 2), und das ist ja auch nichts Neues.

MfG
Binärbaum

Nein. Durch 4n+1 btzw 4n-1 erreichst du weniger Zahlen und dadurch eine höhere Geschwindigkeit.

Das stimmt nicht. Mit 4n+1 und 4n-1 erreicht man ja immer zwei von vier Zahlen, mit 2n+1 eine von zwei Zahlen. Das Verhältnis ist gleich (2/4=1/2). Bei beiden Varianten wird also die Hälfte aller Zahlen betrachtet. Damit ist es egal, welche Variante man nimmt.
(2n+1 ist sogar einfacher, weil man nur eine Formel hat statt zwei.)

MfG
Binärbaum

**negaH**

Suche hier im Forum und du findest meine mathematische Library NMath vom DEC.
Mit ihr ist es nicht nur möglich große Zahlen zu überprüfen sondern man kann auch sehr effizient große industielle Primzahlen erzeugen.

Der beschriebene Algortihmus im obigen Dokument ist gelinde gesagt "lächerlich" ineffizient. Es gibt bei weitem bessere und neuere Verfahren um Primzahlen zu erzeugen.

Als erstes benutzt man eine Art der modularen Siebe die es ermöglichen mit sehr hoher Wahrscheinlichkeit Zahlen zu produzieren die Primzahlen sein könnten. Diese Siebe sind in der Lage ausgehend von einem zufälligen Startwert ganze Gruppen von Divisionen in parallel durchzuführen. Sie liefern dann immer eine Zahl die garantiert nicht durch die Parimzahlen bis 2^16 teilbar sind. Alleine diese Stufe der Erzeugung von Primzahlen filtert 99.99% aller Zusammengesetzten Zahlen raus. Der verbleibende Rest wird nun mit einem strengen Pseudo Primzahl Test überprüft. Dabei ist es aber wichtig welchen Test bzw. Algorithmus man verwendet. Die meisten benutzen ein randomisiertes merstufiges Rabin Miller Verfahren. Dieser Test ist relativ gut aber bei weitem nicht so effizient und sicher wie neuere Verfahren. In meine oben angesprochenen Library benutze ich den sogenannten "Bailie-Selfridge-Wagstaff-Pomerance-Strong-Lucas-Pseudo-Primality-Test". Dieser Test ist sehr modern und wenig bekannt. Der Mathematiker Pomerance hat errechnet das die 1. Zahl die dieser Test als Primzahl ausgibt die aber KEINE Primzahl ist bei Zahlen größer 10^100 liegen wird. Pomerance hat ein Preisgeld von 1000 Dollar ausgesetzt für diejenige Person die eine solche Zahl findet. Bis heute hat kein Mensch eine solche "falsche Primzahl" gefunden.
Das besonder am PBSW Test ist das er NICHT gegen die sogenannten Carmichael Zahlen anfällig ist. Der Rabin Miller Test würde solche Carmichael Zahlen als Primzahlen ausgeben obwohl sie keine sind.

Nungut in jedem Falle produziert man auf diese Art und Weise immer "industrielle" Primzahlen. Deren Wahrscheinlichkeit das sie KEINE primzahlen sind liegt bei unter 1/Ln2(Primzahl), also weit besser als ein normaler Rabin Miller Test.

Erst eine Primzahl Test Algorithmus der ein digitales Prmzahlzertifikat erzeugt kann die Gewissheit schaffen das die Zahl auch wirklich mathematisch bewiesen eine echte Primzahl darstellt. Leider können solche Verfahren, zb. die ECM, bei Primzahlen im Bereichen > 2^512 schon einige Wochen an Rechenzeit verbrauchen.

Nungut im allg. sind industielle Primzahlen absolut ausreichend, besonders in der Kryptoggraphie da dort solche Nicht-Primzahlen leicht durch die kryptographsichen Operationen identifiziert werden.

Die oben angesprochene Sieb-Methode hat entscheidende Vorteile:
1.) sie ist deterministisch und kann demzufolge ausgehend von einem beliebigen Startwert alle succzesiven Primzahlen berechnen
2.) sie kann Primzahlen mit bestimmten Kongruenz-Eigenschaften erzeugen, d.h. also Primzahlen die zb. immer kongruent zu 2 mod 3 oder 3 mod 4 usw. sind. Solche Zahlen benötigt man zb. für bestimmte Verfahren wie RSA, den Quadratischen Restegernerator und viel verschiedene Secret Sharing Systeme wie Asmuth Blom, Rabin Williams usw.
3.) sie kann Primzahlen von spezieller Form produzieren wie zb. die "sarken Primzahlen" oder auch Sophie Germain Primzahlen genannt, produzieren. Diese Primzahlensind von der Form p =2q+1 wobei q ebenfalls eine Primzahl ist. Dies Primes werden zb. für die ElGamal verschlüsselungen/Signaturen benötigt.
4.) sie sind enorm schnell. Um zb. auf meinem P4 1.5Ghz eine 512 Bit Primzahl zu erzeugen benötigt die Software ca. 45 Millisekunden im Durchschnitt. Für eine 1024 Bit Primzahl benötigt sie 400 ms.

Dabei ist aber zu berücksichtigen das das verwendete Verfahren wesentlich stärker ist als ein Rabin Miller oder andere Tests ist. D.h. die Wahrscheinlichkeit das die Zahl auch wirkliche eine Primzahl ist ist um Vielfaches höher.

Wie funktioniert nun die Sieb-Technik ?

Man erzeugt ein Array[x] of Word. Jeder Eintrag in diesem Array bezieht sich auf die kleinen Primzahlen von 3 bis X. Nun nimmt man einen beliebigen 2^i großen Zahlenwert und macht diesen ungerade. Danach berechnet man die Reste zu diesen kleinen Primzahlen von 3 bis X und trägt diese in das Array[] ein. Nun dürfte klar sein das ein Wert im Array[] der == 0 ist bedeutet das diese Zahl teilbar durch diese Primzahl ist. Schön den nun benötigt man nur noch einfachste Additionen und Vergleiche um dieses Sieb upzudaten. Man addiert einfach +2 zu jedem Rest im Sieb und falls dieser Wert größer/gleich der zugehörigen Primzahl sein sollte so muß man logischerweise diese Primzahl vom Rest subtrahieren. Nach jeder Aktualisierung weis man also ob es Reste von 0 gibt und ob die Zahl somit teilbar ist. Der Siebalgo kehrt erst dann zurück wenn alle Reste <> 0 sind. Somit ergibt sich ein Offset den man auf die Startzahl addieren muß. Diese Zahl wird nun noch mit einem starken SPP Test überprüft. Man kann dazu Rabin Miller benutzen oder eben wie in meiner Lib den PBSW-Strong-Lucas Test.

Ist das Sieb sehr groß, zb. alle Primzahlen < 2^16, das wären dann 6541 Einträge im Sieb, dann benutzt man eine andere Methode. Statt bei jedem +2 Schritt alle Reste im Sieb zu berechnen, berechnet man nur die Reste solange sie <> 0 sind und bricht dann ab. Man führt nun einen Offset mit der immer +2 inkrementiert wird. Diesen Offset addiert man auf die Reste und modulo Primzahl wird getestet ob der sich ergebende Rest = 0 ist. Wenn ja bricht man ab und erhöht Offset um +2. Das geht solange bis alle Einträge im Sieb einen Rest <> 0 ergeben. Man hat damit die Gewissheit das die sich aus dem StartWert + Offset ergebende Zahl garantiert nicht teilbar ist durch alle Primzahlen < 2^16. Alle Operationen im Sieb sind aber nur 32 Bit groß und somit wesentlich schneller als direkt mit zb. 512 Bit großen Zahlen zu arbeiten.

Gruß Hagen

**Meflin**

ahhh... auf das habe ich gewartet

Zitat von negaH:

Suche hier im Forum und du findest meine mathematische Library NMath vom DEC.
Mit ihr ist es nicht nur möglich große Zahlen zu überprüfen sondern man kann auch sehr effizient große industielle Primzahlen erzeugen.

toll

Zitat:

Der beschriebene Algortihmus im obigen Dokument ist gelinde gesagt "lächerlich" ineffizient. Es gibt bei weitem bessere und neuere Verfahren um Primzahlen zu erzeugen.

mei, wenn mans halt net besser kennt

...

Zitat:

Bailie-Selfridge-Wagstaff-Pomerance-Strong-Lucas-Pseudo-Primality-Test

öhm ja. genau der

ich finde das teil braucht einen namen. ich nenne es das Meflin-Verfahren

thx jedenfalls