Cryptography Reference
In-Depth Information
8.2 Der Fermat-Test
Obwohl er keine praktische Bedeutung hat, ist der
Fermat-Test
für das Verständnis
sehr hilfreich. Alle im weiteren Text beschriebenen Tests sind vom Fermat-Test
inspiriert.
8.2.1 Der Test
Es sei
n
eine natürliche Zahl ungleich 1. Wir wollen prüfen, ob
n
eine Primzahl
oder zusammengesetzt ist. Man beachte den Satz 6.10 von Fermat. Falls
n
eine
Primzahl ist, so gilt für alle
a
∈{
−
}
1, . . . ,
n
1
die Kongruenz
a
n
−
1
≡
(
)
1
mod
n
.
Damit können wir nun folgende Aussage formulieren:
Gilt
a
n
−
1
≡
1
(
mod
n
)
für ein
a
∈{
2, . . . ,
n
−
1
}
,
so ist
n
garantiert zusammengesetzt.
Mit dieser Aussage gewinnen wir den (probabilistischen)
Fermat-Test
:
∈{
−
}
Wähle ein
a
2, . . . ,
n
1
.
Bestimme
a
n
−
1
modulo
n
(vgl. Abschnitt 6.3 zur schnellen Exponentiation).
Ist
a
n
−
1
≡
(
)
∈
P
1
mod
n
,soist
n
keine Primzahl, gib „
n
“ aus.
Ist
a
n
−
1
≡
1
(
mod
n
)
,soist
n
eventuell eine Primzahl, gib „
n
∈
P
“ aus.
Es ist durchaus möglich, dass die Kongruenz
a
n
−
1
≡
1
(
mod
n
)
erfüllt ist, ob-
wohl
n
keine Primzahl ist. Ist die Kongruenz
a
n
−
1
≡
(
)
aber für
viele
verschiedene
a
erfüllt, so ist die Wahrscheinlichkeit dafür, dass
n
eine Primzahl
ist,
groß
.
1
mod
n
Beispiel
Die Zahl
n
=
341
(=
11
·
31
)
ist keine Primzahl. Der Fermat-Test liefert mit
a
=
2
wegen
2
340
≡
(
)
1
mod 341
,
∈
P
=
zuerst das (falsche) Ergebnis „
n
“. Mit
a
3 folgt dann aber wegen
3
340
≡
56
≡
1
(
mod 341
)
.
die (richtige) Aussage „
n
∈
P
“.
