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

[negaH]

Hi

1.) du bewegst dich im Gebiet der Zahlentheorie er Ganzzahlen. Hier hat die Fließkommaarithmetik nichts zu suchen wenn du nicht sicherstellen kannst das sie auch 100% exakte Resultate liefert:

Zitat:

.....

Delphi-Quellcode:

 while ((u mod 2) = 0) do 
    begin 
      u := Round(u/2); 
      Inc(t); 
    end;

.....

Delphi-Quellcode:

  u := u div 2;
// oder
  U := u shr 1;

wären besser.

oder noch besser gleich optimiert

Delphi-Quellcode:

while odd(u) do 
begin
  u := u shr 1;
  inc(t);
end;

2.) der RM Test muß immer eine Primzahl als Primzahl identifzieren ! Tut er das nicht, dann ist irgendwas falsch an deinem Code. Die Aussage in denen der RM Test sich irrt bezieht sich nur darauf das er eine Zusammengesetzte Zahl als Primzahl ausgeben kann. Das sind dann meistens Carmichael Zahlen.

3.) hier im Forum solltest du ein besseren Ersatz für obige FIsPrimeNPA() finden, der schneller ist und zudem nicht mit der schlechst möglichen Komplexität arbeitet.

4.) du musst im RM Test nicht mit einem zufalls A rechnen. Es reicht zb. mit den kleinen Primzahlen beginnend mit 2 bis X als A zu arbeiten.

5.) ab diesem Moment kannst du dein Verfahren so abändern das es sequientiell die Zahlen durchgeht

[edit]

Alles schon mal da gewesen, suche !

http://www.delphipraxis.net/internal...ation&start=10
http://www.delphipraxis.net/internal...=exponentation

[/edit]

Gruß Hagen