HP 39g-Grafenberechner - Handbuch (Seite 168)

Exakte Berechnungen und Mathematik mit HP40G
168 Arithmetische Programme
Natürlich wird diese Methode zwecks Feststellung, ob die großen Zahlen
Pseudo-Primzahlen sind, benutzt.
8.6.1 Algorithmische Übersetzung
Es wird folgendes vorausgesetzt:
Der Zufall (N) gibt eine ganze Zahl zufällig zwischen 0 und N – 1.
Berechnung:
K
N – 1
mod N
Wird durch den Algorithmus der schnellen Potenz durchgeführt (siehe Seite
81).
Man registriert:
Puismod (K, P, N) Funktion, die K
P
mod N rechnet
Funktion Ist eine Primzahl (N)
lokal K, I, P
1-
>I
1-
>P
solange P = 1 und I < 20 durchführen
Zufall (N–2)+2-
>K
Puismod (K, N–1, N)-
>P
I+1–
>I
/solange/
Wenn P =1 so
Das Ergebnis ist richtig
sonst
ist das Ergebnis falsch
/wenn/
/Funktion/