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

Thema durchsuchen

Ansicht

Themen-Optionen

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

Ein Thema von St.Pauli · begonnen am 20. Dez 2005 · letzter Beitrag vom 21. Dez 2005

Vorheriger Beitrag

Nächster Beitrag

Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
1.088 Beiträge

Delphi XE2 Professional

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

20. Dez 2005, 20:58

Hallo St.Pauli,

im Pseudo Code steht

markieren

Delphi-Quellcode:

			a:=Random(1, n-1)

if Witness(a,n) then

Die dort benutze Random Version, so denke ich, gibt eine Zufallszahl im Bereich 1 .. n-1 aus.
Der Parameter a ist also minimal 1, maximal n-1

In Deiner Version wolltest du das a:= .... sparen und ersetzt den Parameter a durch
Random(n-2) + 1 Random(n-2) ergibt eine Zufallszahl im Bereich 0 .. n-3.
Hierzu addierst du 1, erhältst also einen Wert im Bereich 1..n-2
Dein Parameter a ist minimal 1, maximal n-2

Vielleicht liegts daran?!