Cryptography Reference
In-Depth Information
spricht man von einem
Fermat-Zeugen
.
Nun könnte man vermuten, dass ein guter Primzahltest der folgende wäre: Wähle
zunächst
a
∈{
2
,...,n
−
2
}
zufällig und teste, ob
a
ein Zeuge ist; wie man leicht sieht,
sind
a
=1
und
a
=
n
−
1
nie Zeugen. Ist dies der Fall, so gib »zusammengesetzt« aus,
sonst »prim«.
In der Tat sieht dieser Test zunächst vielversprechend aus, denn es gilt:
∈
Z
n
ein Fermat-Zeuge. Dann
Lemma 6.3.8.
Es sei
n>
2
eine ungerade Zahl und sei
a
Z
n
Fermat-Zeugen.
sind mindestens die Hälfte der Elemente in
Beweis.
Man kann sich mit Hilfe von Lemma 6.3.1 leicht überlegen, dass
U
=
{b ∈
{
Z
n
bildet: Sie enthält das
Einselement
1
und ist unter Multiplikation abgeschlossen. Wegen
a/
b
n−
1
mod
n
=1
1
,...,n
−
1
}|
}
eine Untergruppe von
∈
U
ist
U
eine echt
e
Z
n
. Nun erhalten wir die Behauptung aus Folgerung 6.3.2.
Untergruppe von
∈
Z
n
, so ist die Wahrscheinlichkeit, einen Fermat-Zeugen
zu »erwischen«, wenn man zufällig ein Element aus
Existiert ein Fermat-Zeuge
a
Z
n
wählt, also recht groß. Genauer
φ
(
n
)
2
n
ist sie
≥
, da bekanntlich
φ
(
n
)=
|
Z
n
|
gilt. Aus dem Beweis zu Folgerung 6.3.3
φ
(
n
)
2
n
1
2
·
(1+log
n
)
folgt weiter
. Diese Wahrscheinlichkeit kann man durch wiederholtes
Raten eines Zeugen sehr schnell, nämlich exponentiell, steigern (siehe das Beispiel nach
Folgerung 6.3.3 sowie Aufgabe 5.7.16 zur Wahrscheinlichkeitsverstärkung). Damit wäre
bereits der Fermat-Test, der nur Bedingung 2. in Lemma 6.3.7 überprüft, ein sehr guter
Primzahltest.
In der obigen Argumentation sind wir davon ausgegangen, dass wenigstens ein Fermat-
Zeuge
a
≥
∈
Z
n
existiert. Leider gibt es unendlich viele ungerade, zusammengesetzte Zahlen
n
,die
keinen
solchen Zeugen besitzen, sogenannte Carmichael-Zahlen:
Definition 6.3.3 (Carmichael-Zahlen). Eine ungerade, zusammengesetzte Zahl
n
ist
eine
Carmichael-Zahl
, falls
a
n−
1
mod
n
=1
für alle
a
∈
Z
n
gilt.
Für Carmichael-Zahlen ist der Fermat-Test unbrauchbar: Für eine Carmichael-Zahl
n
ist
a
n−
1
mod
n
=1
für »fast« alle Zahlen
a
in
{
1
,...,n−
1
}
erfüllt, nur für
a∈
Z
n
nicht
- sonst wäre
a
n−
2
mod
n
wegen
a
a
n−
2
mod
n
=1
das inverse Element zu
a
·
∈
Z
n
,und
also
a ∈
Z
n
.AbervonZahlen
a
∈
Z
n
, und also ggT
(
a, n
)
=1
,
gibt es nicht viele, wenn
n
nur wenige Primfaktoren besitzt, was durchaus der Fall sein
kann. Auf einen Zeugen
a
∈{
1
,...,n
−
1
}
mit
a/
∈
Z
n
zu treffen, wäre in der Tat ein
großer Glückstreffer, denn ggT
(
a, n
)
wäre ein nicht-trivialer Faktor von
n
.Manwürde
also sicher wissen, dass
n
keine Primzahl ist und hätte sogar einen Faktor gefunden.
Da der Fermat-Test also für Carmichael-Zahlen versagt, schauen wir uns Bedingung 1.
von Lemma 6.3.7 genauer an. Leider müssen wir für diese Bedingung Folgendes festhalten:
In Bedingung 1. geht es darum, eine Wurzel von
1
in
∈{
1
,...,n
−
1
}
mit
a/
Z
n
zu finden, die nicht
1
oder
−
1
mod
n
ist. Mit dem Chinesischen Restsatz (Satz 6.3.1) kann man sich aber leicht
überlegen, dass es davon nicht viele geben kann, falls
n
nur wenige Primfaktoren aufweist:
Ist zum Beispiel
n
=
p
q
für zwei verschiedene Primzahlen
p
und
q
, dann sind die
einzigen Wurzeln von
1
solche Zahlen
a ∈{
1
,...,n−
1
}
·
, für die
a
mod
p ∈{
1
,p−
1
}
und
gilt. Davon gibt es allerdings nur
2
2
=4
viele(sieheAufgabe6.7.6).
a
mod
q
∈{
1
,q
−
1
}
