Cryptography Reference
In-Depth Information
Fällt der Fermat-Test für viele
a
∈{
2, . . . ,
n
−
1
}
positiv aus, d. h., es gilt
a
n
−
1
≡
(
)
,soist
n
wahrscheinlich eine Primzahl. Würde man alle mög-
lichen Zahlen
a
testen, so wäre der Test sogar deterministisch (aber aufwändiger
als die Probedivision), das folgt aus:
1
mod
n
Lemma 8.1
Für ein a
∈{
1, . . . ,
n
−
1
}
gelte
ggT
(
a
,
n
)
=
1
. Dann gilt
a
n
−
1
≡
(
)
1
mod
n
.
Beweis.
Angenommen, es gilt
a
n
−
1
≡
(
)
∈
Z
1
mod
n
. Dann gibt es ein
r
m
it
a
n
−
1
+
rn
=
1. Nach Lemma 4.8 (d) gilt dann ggT
(
a
,
n
)=
1.
Korollar 8.2
Ist die Kongruenzgleichung a
n
−
1
≡
(
)
∈{
−
}
1
mod
n
für alle a
1, . . . ,
n
1
erfüllt, so
ist n eine Primzahl.
Beweis.
Nach Lemma 8.1 sind für jedes
a
∈{
1,...,
n
−
1
}
die Zahlen
a
und
n
teilerfremd. Folglich ist
n
eine Primzahl.
8.2.2 Pseudoprimzahlen und Zeugen für Zusammengesetztheit
Gilt für eine zusammengesetzte Zahl
n
und ein
a
∈{
2, . . . ,
n
−
1
}
die Kongruenz
a
n
−
1
≡
(
)
1
mod
n
,
so heißt
n
Pseudoprimzahl
zur Basis
a
. Man beachte, dass Pseudoprimzahlen
keine Primzahlen sind. Genauer lässt sich sagen: Eine Pseudoprimzahl ist eine
natürliche Zahl
n
, die beim Fermat-Test fälschlicherweise „
n
∈
P
“ liefert.
Beispiel
Zur Basis
a
=
2 gibt es zwischen 2 und 2 000 nur die sieben Pseudoprimzahlen
341, 561, 645, 1 105, 1 387, 1 729 und 1 905.
Eine Zahl
a
, die
a
n
−
1
≡
1
(
mod
n
)
erfüllt, nennt man auch
Zeuge
dafür, dass
n
=
zusammengesetzt ist. So ist z. B.
a
3 ein Zeuge der Zusammengesetztheit von
341 (vgl. das Beispiel auf Seite 144). Man beachte, dass der Zeuge in unserem
Beispiel keinen Hinweis auf einen Primteiler von
n
gibt.
Bemerkung
ImAllgemeinen sind Zeugen mathematische Größen, mit denen eine Eigenschaft
effizient
bewiesen
werden kann. Häufig sind sie nicht leicht zu finden.
