Miller-Rabin - Eigene Impl. findet nicht jede Primzahl...

[negaH]

Zitat:

Nur waren danach alle anderen Zahlen zusammengesetzt. Wie kann das sein? Hängt der Fehler wirklich an der Größe der Variabeln?

x := (d * d) mod n

wenn D vom Typ Cardinal ist wie groß darf er maximal sein damit das Resultat von D * D noch in einen Cardinal reinpasst ?

Am besten mal mit D = 2,4,8,16,32,64 usw. testen, sprich also mit D = 2^i wenn i von 0 bis 31 geht.

Oder andersrum

Wenn a = b^2 dann ist b = a^0.5 = Sqrt(a).

Ergo was ergibt Sqrt(MaxInt) und was ergibt Sqrt(MaxCardinal).

D darf also niemals größer als Sqrt(2^32) = 2^16 sein. Wenn aber nun D modular N genommen wird kann D nur dann größer als 2^16 werden wenn N ebenfalls größer 2^16 ist. Ergo: mit deiner Implementation kannst du nur bis 2^16 ordentlich arbeiten.

Ich hatte es Klaus schon per PN mitgeteilt, schau mal hier rein

http://www.delphipraxis.net/internal...prime&start=20
http://dennishomepage.gugs-cats.dk/IsPrimeChallenge.htm
http://primes.utm.edu/prove/prove2_3.html


Gruß Hagen