Tweet
Hallo Leute,
ich suche eine effiziente Lösung, um in PHP große Primzahlen (allerhöchstes Maximum sind ca. 120 Stellen, mehr brauche ich nicht) zu erzeugen.
z.Zt. erzeuge ich eine große Zufallszahle (ungerade) und teste, ob diese Zahl eine Primzahl ist. Dazu nehme ich den Fermat-Test.
Der Fermat-Test geht wie folgt.
Wenn 2^(n-1) mod n = 1, dann ist n eine Primzahl.
In einigen PHP Versionen ist bcpowmod schon implementiert, in anderen noch nicht, dann muss man es in php implementieren.
Falls die Zahl keine Primzahl ist, addiere ich 2 dazu und teste wieder, bis ich eine Primzahl finde. Das Problem bei dem Ganzen ist die Performance. Manchmal hat man Glück und liegt mit der Zufallszahl dicht neben einer Primzahl sodass nur ein paar Mal getestet werden muss und manchmal muss man ein paar hundert Tests durchführen. Und mein Primzahltest von oben ist in php nicht gerade schnell. Bei sehr sehr kleinen Zahlen geht es ja noch einigermaßen. Aber bei Zahlen wie 1546255733086197899652914449938053774373736611225094826481407302309289890044525493906099655458365041 403140043571 braucht die Funktion 1,6 Sekunden um zu testen, ob es eine Primzahl ist oder nicht (auf einem AMD K6-III 400 MhZ).
Also nochmal meine Bitte von oben: Wer kennt einen effizienten Weg um große Primzahlen zu erzeugen?
Ich habe mal in den C-Sourcecode von openssl reingeschaut, kapiere es allerdings nicht so ganz.
ich suche eine effiziente Lösung, um in PHP große Primzahlen (allerhöchstes Maximum sind ca. 120 Stellen, mehr brauche ich nicht) zu erzeugen.
z.Zt. erzeuge ich eine große Zufallszahle (ungerade) und teste, ob diese Zahl eine Primzahl ist. Dazu nehme ich den Fermat-Test.
Der Fermat-Test geht wie folgt.
Wenn 2^(n-1) mod n = 1, dann ist n eine Primzahl.
PHP-Code:
function isPrime($n)
{
return ((bcpowmod(2,bcsub($n,1),$n)!="1") ? false : true);
}
Falls die Zahl keine Primzahl ist, addiere ich 2 dazu und teste wieder, bis ich eine Primzahl finde. Das Problem bei dem Ganzen ist die Performance. Manchmal hat man Glück und liegt mit der Zufallszahl dicht neben einer Primzahl sodass nur ein paar Mal getestet werden muss und manchmal muss man ein paar hundert Tests durchführen. Und mein Primzahltest von oben ist in php nicht gerade schnell. Bei sehr sehr kleinen Zahlen geht es ja noch einigermaßen. Aber bei Zahlen wie 1546255733086197899652914449938053774373736611225094826481407302309289890044525493906099655458365041 403140043571 braucht die Funktion 1,6 Sekunden um zu testen, ob es eine Primzahl ist oder nicht (auf einem AMD K6-III 400 MhZ).
Also nochmal meine Bitte von oben: Wer kennt einen effizienten Weg um große Primzahlen zu erzeugen?
Ich habe mal in den C-Sourcecode von openssl reingeschaut, kapiere es allerdings nicht so ganz.
Moderator
Kommentar