Cryptography Reference
In-Depth Information
Da ggT
(
a
,
n
)=
1, gilt nach Voraussetzung
a
n
−
1
≡
(
)
1
mod
n
.
Nach (iii) in Lemma 6.1 (b) ist
p
α−
1
(
−
)
−
p
1
ein Teiler von
n
1. Damit folgt (i)
unmittelbar. Wegen
p
α
|
n
gilt
α
=
1, sonst wäre nämlich
p
ein Teiler von
n
−
1
und von
n
und somit von 1. Daher gilt auch (ii).
(2)
⇒
(1): Es sei
a
∈{
2, . . . ,
n
−
1
}
mit ggT
(
a
,
n
)=
1 gegeben. Für alle Primteiler
p
von
n
gilt die Kongruenz
a
p
−
1
≡
(
)
1
mod
p
aufgrund des Satzes 6.10 von Fer-
1 gilt also auch
a
n
−
1
a
n
−
1
mat. Wegen
p
−
1
|
n
−
≡
1
(
mod
p
)
,d.h.
p
|
−
1 für al
le
a
n
−
1
1, d. h.
a
n
−
1
|
|
−
≡
(
)
p
n
. Weil
n
quadratfrei ist, folgt hieraus
n
1
mod
n
.
Wir ziehen noch eine Folgerung, die wir später benötigen werden.
Korollar 8.5
Ist n eine Carmichael-Zahl, so ist n ein Produkt von mindestens drei (verschiedenen)
Primzahlen.
=
>
Beweis.
Wir nehmen an, dass
n
pq
mit Primzahlen
p
q
gilt. Wegen Satz 8.4
gilt
p
−
1
|
pq
−
1
=(
p
−
1
)
q
+
q
−
1,
woraus der Widerspruch
p
−
1
|
q
−
1 folgt.
Bemerkung
Es gibt unendlich viele Carmichael-Zahlen. Das wurde in [1] von W. Alford, A.
Granville und C. Pomerance bewiesen. Die kleinsten Carmichael-Zahlen sind
561
=
3
·
11
·
17, 1 105
=
5
·
13
·
17, 1 729
=
7
·
13
·
19.
8.3 Der Miller-Rabin-Test
Der
Miller-Rabin-Test
ist ein probabilistischer Primzahltest. Im Unterschied zum
Fermat-Test kann man die Wahrscheinlichkeit dafür abschätzen, dass eine unter-
suchte Zahl
n
eine Primzahl ist. Nach
t
positiven Tests ist diese Wahrscheinlich-
keit größer gleich 1
t
.
−
(
)
1/4
8.3.1 Das Verfahren
Gegeben ist eine ungerade natürliche Zahl
n
, von der wir entscheiden wollen,
ob
n
eine Primzahl ist oder nicht. Wir legen in diesem Abschnitt zwei weitere
natürliche Zahlen
s
und
d
fest, die durch die folgende Gleichung bestimmt sind:
2
s
d
mit 2
n
−
1
=
d
.
