Andreas Wilhelm schrieb:
> Ich habe gestern Abend im
> Thread zum Thema "Verschlüsselung" den Hinweis auf den Miller-Rabin Test
> erhalten und diesen nun implementiert. Leider habe ich nun zwei
> Probleme.
>
> Zum einen findet der Algorithmus keine Primzahlen und zum anderen weiß
Problem ist wohl der Wertebereich. Da du long multiplizierst, ist der
Wertebereich effektiv auf 2^16 begrenzt. Zumindest in deiner momentanten
Implementierung
> ich nicht, wie ich über 32 Bit Integer hinaus kommen kann.
Du brauchst eine lange Arithmetik. Also entweder auf die Suche gehen
oder selber klöppeln. Es bietet sich an, Zahlen zur Basis 2^32 oder 2^31
zu verwenden; die einzelnen Ziffern sind dann zB longs.
Die Arithmetik ist zu implementieren über A=Z/nZ für eine natürliche
Zahl n. Du brauchst:
- Addition, Subtraktion, Multiplikation: A×A → A
- Wahrscheinlich Division: A×A* → A mit Ausnahmebedandlung
für den Fall daß Divisor und Modul n nicht teilerfremd sind
- Exponentiation A×N → A
- Division mit Rest N×N -> N×N
- Wurzel N → N
- Erweiterter Euklidischer Algorithmus
Primzahlen finden geht üblicherweise so:
1) Zufällig eine Zahl gewünschter Größenordnung wählen
2) Probedivision durch kleine natürliche Zahlen. Ggf. ist
GGT-Berechnung mit zB 2·3·5·7·11·13·... schneller als alles einzeln
zu Dividieren.
3) Pseudoprimzahl-Tests wie Miller-Rabin zu mehreren Basen
4) Beweis der Primalität, zB Goldwasser-Kilian-Atkin,
Elliptische Kurven, etc.
Schritt 4 wird mit Abstand die meiste Zeit verbraten.
Ist p eine potentielle Primzahl, dann lässt sich die Primalität leicht
zeigen (oder widerlegen, etwa weil eine Division mod n nicht
durchführbar ist), wenn es gelingt, p-1 zu faktorisieren. IdR sind
solche Zahlen jedoch kryptographisch schwach, daher sollte man prüfen,
ob p-1 leicht faktorisierbar ist oder nicht. Um zu sehen, daß es nicht
leicht faktorisierbar ist: kleine Faktoren rausteilen, dann Pollard's
Rho-Methode, Elliptische-Kurven-Methode darauf los lassen und wenn keine
Faktorisierung gelingt ist p ok.
Weiterhin kann man sich auch Primzahlen "konstruieren". Dazu setzt man
mit zwei nicht zu kleinen Primzahlen
Man hangelt sich also hoch: Die r sind kleine Primzahlen. Die q sind
aufgrund ihrer Konstruktion leicht als prim oder nichtprim zu
identifizieren, ditto für p.
p-1 zerfällt nicht in kleine Primzahlen; allerdings kann ich nicht
sagen, ob es aufgrund dieser Konstruktion andere Haken und Ösen gibt,
was die kryptographische Stärke herabsetzt.
Siehe auch
http://en.wikipedia.org/wiki/Primality_certificate
