Erst die schlechte Nachricht, obiger Source ist ein Cut aus meiner Contributation zum FastCode Projekt, und wie üblich: er ist fehlerhaft. Anbei also die korregierte Version. Denn ich bon stutzig geworden als du schriebst das der Test "nur" 100 mal schneller als euer sein sollte. Er sollte nämlich bei weitem schenller laufen. Am besten mal alle ungeraden Zahlen von 1 bis 2^32-1 in einer Schleife durchlaufen lassen und die gemessene Zeit dann durch 2^31 teilen. Das ergibt dann den korrekten Zeitbedarf beider Verfahren.
Zitat:
Fermat-Test vorschalten, aber scheiterte eben an diesem a^n mod (n-1)...
Dieser Test ist veraltet und stellt die Basis des Rabin-Miller Verfahrens dar. Besser ist ein Strong Probable Pseudo Prime Test zu festen Basen.
Statt also a^n mod (n-1) wird folgenes benutzt:
N-1 = 2^s * d -> also s ist die Anzahl der trailing Null Bits in N. Man wird also N-1 solange rechts shiften wir das unterste Bit 0 ist. Dabei zählt man S in jedem Schritt +1 höher.
Nun folgt mit diesem zu ermitteltem d die modulare Exponentation bis
a^d == 1 mod n
oder
(a^d)^2^r == -1 mod n
ist, r wird dabei von 0 bis s iteriert. Die Kongruenz von == -1 mod N wird in positiven modularen Ringen vereinfacht dadurch das -1 mod N == (N -1) ist.
Gruß hagen