Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
aufg. 32 primzahlen & zertifikate
hm primzahlen und zertifikate:
da will man doch nur eine zahl als beweis finden, die uns “sagt”, dass die zahl n primzahl.
ist aber im endeffekt das gleiche wie der miller-rabin-test
oder bin ich da auf dem irrweg.
wie macht man es am besten, bei so hohen potenzen die modulo-zahlen zu berechnen.
gibt es ein rezept. tu mich da etwas schwer…
Fermat und Miller Rabin sind zwei paar Schuhe.
Der Fermat sagt, dass p keine Primzahl ist, wenn (a^(n-1) mod n) ≠ 1 ist. Aber nicht jedes a muss nachweisen, dass n nicht prime ist. Beispiel
n = 25, a = 7:
7^24 mod 25 = 1
25 ist aber bekanntlich keine Primzahl…
Für ein anderes a klappts aber:
2^24 mod 25 = 16
Also ist 2 eine Zeuge, 7 nicht,
Es gibt aber Pseudoprimzahlen, für die der Fermat-test nie nachweisen kann, dass sie keine Primzahlen sind (Carmichael Zahlen) also für alle a niemals Zeugen findet.
Der Miller-Rabin Test macht etwas anderes. Der rechnet auch a^(n-1) mod n aus, allerdings mit schneller Exponentiation. Dabei verwendet er die Idee, dass der Zn nur dann ein Körper ist, wenn n prime ist. Ist dagegen n keine Primzahl, dann ist der Restklassenring modulo n kein Körper, da die Restklasse jedes echten Teilers von n ein Nullteiler ist, welcher kein Inverses bezüglich der Multiplikation besitzt. (Aber das Inverse braucht es um ein Körper zu sein)
Der Test berechnet also in der schnellen Exponentiation immer wieder x² mod n. Passiert einmal der Fall, dass x² mod n = 1 ergibt, dann muss geprüft werden ob x = 1 war oder x = -1 = n-1. Denn die Gleichung hat ja nur die zwei Lösungen, wenn Zn ein Körper ist. Tritt aber der Fall ein, dass x etwas anderes war, so ist klar, Zn kein Körper, also n nicht prime.
Sollte bei der schnellen Exponentiation so ein Fall nicht aufgetreten sein, so führt man mit dem Ergbnis noch den Fermat Test durch (man hat ja a^(n-1) ausgerechnet).
Sollte der auch kein Ergebnis liefern so geht man von der Primheit der Zahl n aus.
Der Miller-Rabin hat den Vorteil, dass er auch die Carmichael Zahlen korrekt als Zusammengesetzt erkennt.
Das geht nur mit schneller Expo relativ flott. Der Strehl hat seine Lösungen auch immer mit Maple ausgerechnet…
Zertifikate für Primzahlen
Zertifikate für Primzahlen haben mit den Primzeugen oder dem Miller, Fermat oder Eulertest gar nichts zu tun! Ein Zeuge sagt wie ja gerade von Erik demonstriert dass eine Zahl keine Primzahl ist.
Das Zertifikat aber dient dazu, zu beweisen dass eine Zahl p prim ist.
Dazu versucht man ein sogenanntes primitives Element in dem zugehörigen Körper Zp zu finden. Das heißt ein Element a das die selbe Ordnung ||hat, wie Phi(p).
Wenn also p eine Primzahl ist, ist Zp ein endlicher Körper und ein endlicher Körper muss solche primitiven Elemente enthalten.
Das ganze Verfahren, wie man das Zertifikat findet, steht auf den Folien vom 20. Dezember und ist nicht so schwer.