Zitat:
Wenn ich mal ganz doof fragen darf. Wie kann man eine 1024Bit große Primzahl erzeugen? Leben wir nicht in einer 32Bit Welt?
Dazu benötigt man eine mathematsiche Bibliothek die mit solchen Zahlen rechnen kann. Mein eigene Entwicklung geht nun über 3 Jahre hinweg, und hatte zum Erfolg das sie zB. 1 Million Dezimalstellen von Pi als dritt schnellste PC Software der Welt errechnen kann.
Jede 32 Bit Operation, wie Addition,Subtraktion,Multiplikation usw. kann verkettet werden um 64,96,128... Bit Zahlen zu berechnen. Dafür haben die Konstrukteure der Chipsätze schon Sorge getragen.
D.h. statt nur 32Bit zu speichern, speichert man z.B. 32*32Bit hinereinander, also eine 1024 Bit Zahl. Alle Operationen werden nun auf 32Bit Operationen heruntergebrochen. Eventuelle Überläufe einer 32Bit Opration werden als Übertrag in die nächsthöhere 32 Bit Operation übernommen. Man kann sich das so vorstellen als wenn man 4 * 8Bit addieren wollte. Eine 32Bit Addition würde dann mit den 4 * 8 Bit's eines 32Bit Wertes das gleiche machen.
Hat man die Grundrechenoperationen einmal für beliebig große Zahlen programmiert, kann man nun die fehlenden mathematischen Algorithmen programmieren. Zum Erzeugen von "Primzahlen" benötigt man GCD() = Größter gemeinsammer Teiler, Modulare Inversionen per erweitertem GCD, die modulare Exponentation usw. Nun entwickelt man die Algorithmen zur "Primzahl" Erzeugung. Am häufigsten dürfte der Rabin Miller Test sein, der effizient aber nicht der optimalste Algo. ist. In meiner Library nutze ich einen "Strong-Lucas-Pseudo-Primzahl-Test" von Baillie-Selfridge-Wagstaff-Pomerance.
Man erzeugt also keine echten und eindeutigen Primzahlen, sondern sogenannte Strenge-Pseudo-Primzahlen. Die Wahrscheinlichkeit das eine so erzeugte 1024 Bit Zahl keine Primzahl ist, beträgt 1/2^1024. D.h. es kann durchaus vorkommen das eine solche "industrielle" Primzahl garkeine Primzahl ist. Zb. der Rabim Miller test lässt sogenannte Carmichel-Zahlen durch. D.h. der RM Test sagt bei diesen Zahlen das es eine Primzahl ist obwohl es keine ist. Der BSWP Test erkennt solche Carmichelzahlen. Seit Erfindung dieses Testes, 10 Jahren alt, hat man noch keine einzigste Nicht-Primzahl gefunden die diesen Test als Primzahl besteht. Man vermutet das die erste dieser Zahlen weit über 10.000 Bits groß sein muß. Promerance, einer der Professoren die dieses Verfahren analysierten, hat ein Preisgeld von 1.000 Dollar ausgesetzt für denjenigen der die erste solche Zahl findet. Bis heute hat er die Scheine noch
Gruß Hagen