[C++] Primzahlen Tests

[Andreas W. (avedo)]

Guten Abend!

Ich beschäftige mich momentan mit verschiedenen 
Verschlüsselungsverfahren und somit auch mit der Generierung von 
Schlüsseln, im aktuellen Fall Primzahlen.

Zu diesem Zweck ist es notwendig möglichst schnell eine potentielle 
Primzahl zu finden und diese dann auf ihre Korrektheit zu prüfen.

Das Testen auf eine Primzahl ist bisher kein Problem. Ich verwende dazu 
das Sieb des Eratosthenes (siehe Beispielprogramm im Anhang). Die Suche 
einer Potentiellen Primzahl ist jedoch viel zu langsam. Ich wollte die 
Suche eigentlich auf Basis des kleinen Fermat implementieren, jedoch 
habe ich gehört, dass es deutlich schnellere Verfahren geben soll.

Würde mich freuen, wenn ihr mir ein paar Verweise auf möglichst 
effiziente Verfahren geben könntet. Auch freue ich mich über Anregungen 
bezüglich der bisherigen Implementation. Um so schneller der Test um so 
besser.

Vielen Dank.

Liebe Grüße,

Andreas

EDIT: Mir ist gerade aufgefallen, dass es natürlich keinen Sinn macht in 
der getRandom() Funktion die Funktion srand aufzurufen. Mache das nun in 
der main(), konnte aber leider den neuen Quellcode nicht hochladen.

[Andreas W. (avedo)]

Guten Morgen!

Bitte entschuldigt das doppelte Posting. 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ß 
ich nicht, wie ich über 32 Bit Integer hinaus kommen kann.

Wäre super, wenn sich jemand das Programm mal ansehen könnte. Habe ein 
komplettes Beispiel inklusive einem Makefile als *.tar.gz angehängt.

Liebe Grüße,

Andreas

[Johann L. (gjlayde)]

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

$$p = 1+q_1\cdot q_2$$

mit zwei nicht zu kleinen Primzahlen

$$q_i = 1 + \prod_j r_{j,i}$$

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

[Horst H. (horha)]

Hallo,

GMP: The GNU Multiple Precision Arithmetic Library
kann doch den Miller Rabin test und so vieles andere mehr in Bezug auf 
Primzahlen und Kryptografie.

http://gmplib.org/