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