HP 39g-Grafenberechner - Handbuch (Seite 167)

Exakte Berechnungen und Mathematik mit HP40G
Arithmetische Programme 167
5-
>I:
FLOOR (
¥1  >J:
WHILE I
” - $1' 3 5(3($7
IF N MOD I= =0 OR N MOD I+2= =0 THEN
0 -
>P:
ELSE
I+6-
>I:
END:
END:
CLEAR:
DISP 5;P:
FREEZE:
8.6 Wahrscheinlichkeitsmethode des Herrn
Rabin
Wenn N eine Primzahl ist, dann sind alle Zahlen K, kleiner als N, Primzahlen
mit N, somit (laut Fermatssatz) bekommt man folgendes:
K
N – 1
= 1 (mod N)
Wenn N keine Primzahl ist, so sind die ganzen Zahlen K ausgerechnet nach
der Formel:
K
N – 1
= 1 (mod N)
wenig zahlenmäßig.
Man kann genauer zeigen, daß wenn N > 4 ist, so ist die Wahrscheinlichkeit
eine solche Zahl K zu bekommen kleiner als 0,25.
Die Zahl N, die K
N – 1
= 1 (mod N) auf 20 Zyklen K kontrolliert (prüft), ist eine
Zahl - eine Pseudoprimzahl. Die Wahrscheinlichkeitsmethode des Herrn Rabin
beruht auf einer Zufallsauswahl der Zahl K (1< K <N) und auf der Berechnung:
K
N – 1
(mod N)
Wenn K
N – 1
= 1 (mod N) ist, wird eine neue Auswahl durchgeführt und wenn
K
N – 1   PRG 1  NDQQ PDQ VLFK VLFKHU VHLQ GD‰ 1 NHLQH 3ULP]DKO LVW
Wenn man für K
N – 1
= 1 (mod N) auf 20 Auswahlen K bekommt, kann man
zum Schluß gelangen, daß N eine Primzahl ist und das mit einer geringen
Irrtumswahrscheinlichkeit, die 0.25
20
nicht überschreitet, das bedeutet ca. 10
–12
.