<< . .

. 19
( : 33)



. . >>

Man kennt bisher 47 Mersenne™sche Primzahlen, die größte ist
243.112.609 ’ 1 , sie hat 12 978 189 Dezimalstellen.
Für den neuesten Stand vgl. man http://www.mersenne.org/. Auch von den
Mersenne™schen Primzahlen ist nicht bekannt, ob es unendlich viele gibt.
Um zu testen, ob eine Zahl der Form 2n ’ 1 von solch riesiger Größenordnung
eine Primzahl ist, stehen spezielle Methoden zur Verfügung. Die im vorliegenden
Kapitel diskutierten Primzahltests versagen schon bei weit kleineren Zahlen.
144 8 Primzahltests

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

an’1 ≡ 1 (mod n) .

Damit können wir nun folgende Aussage formulieren:


Gilt an’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 an’1 modulo n (vgl. Abschnitt 6.3 zur schnellen Exponentiation).

Ist an’1 ≡ 1 (mod n), so ist n keine Primzahl, gib „n ∈ P“ aus.

Ist an’1 ≡ 1 (mod n), so ist n eventuell eine Primzahl, gib „n ∈ P“ aus.

Es ist durchaus möglich, dass die Kongruenz an’1 ≡ 1 (mod n) erfüllt ist, ob-
wohl n keine Primzahl ist. Ist die Kongruenz an’1 ≡ 1 (mod n) aber für viele
verschiedene a erfüllt, so ist die Wahrscheinlichkeit dafür, dass n eine Primzahl
ist, groß.

Beispiel
Die Zahl n = 341 (= 11 · 31) ist keine Primzahl. Der Fermat-Test liefert mit a = 2
wegen
2340 ≡ 1 (mod 341) ,
zuerst das (falsche) Ergebnis „n ∈ P“. Mit a = 3 folgt dann aber wegen

3340 ≡ 56 ≡ 1 (mod 341) .

die (richtige) Aussage „n ∈ P“.
8.2 Der Fermat-Test 145

F¤llt der Fermat-Test für viele a ∈ {2, . . . , n ’ 1} positiv aus, d. h., es gilt
an’1 ≡ 1 (mod n), so ist 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:

Lemma 8.1
Für ein a ∈ {1, . . . , n ’ 1} gelte ggT(a, n) = 1. Dann gilt

an’1 ≡ 1 (mod n) .

Beweis. Angenommen, es gilt an’1 ≡ 1 (mod n). Dann gibt es ein r ∈ Z mit
an’1 + r n = 1. Nach Lemma 4.8 (d) gilt dann ggT(a, n) = 1.

Korollar 8.2
Ist die Kongruenzgleichung an’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

an’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 an’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
Im Allgemeinen sind Zeugen mathematische Größen, mit denen eine Eigenschaft
ef¬zient bewiesen werden kann. H¤u¬g sind sie nicht leicht zu ¬nden.
146 8 Primzahltests

Es gibt ungerade zusammengesetzte natürliche Zahlen n, die für den Fermat-Test
besonders ungünstig sind. Diese sogenannten Carmichael-Zahlen haben die Eigen-
schaft, dass der Fermat-Test für alle a ∈ {1, . . . , n ’ 1}, die keinen gemeinsamen
Teiler mit n haben, positiv ausf¤llt. Carmichael-Zahlen sind also nach Lemma 8.1
die denkbar ungünstigsten Zahlen für den Fermat-Test.



8.2.3 Carmichael-Zahlen

Für eine Pseudoprimzahl n zur Basis a liefert der Fermat-Test „n ∈ P“, obwohl
n keine Primzahl ist. Eine natürliche Zahl n heißt Carmichael-Zahl, wenn sie
Pseudoprimzahl zu allen Basen a ∈ {2, . . . , n ’ 1} mit ggT(a, n) = 1 ist.

Beispiel
Es ist 561 = 3 · 11 · 17 eine Carmichael-Zahl. Es gilt n¤mlich für alle a ∈
{2, . . . , 560} mit ggT(a, 561) = 1 die Kongruenz an’1 ≡ 1 (mod 561).

Gerade Carmichael-Zahlen existieren nicht.

Lemma 8.3
Jede Carmichael-Zahl ist ungerade.

Beweis. Angenommen, die Carmichael-Zahl n ist gerade. Die Zahl a = n ’ 1 ist
zu n teilerfremd, ggT(n ’ 1, n) = 1. Weil n eine Carmichael-Zahl ist, gilt

’1 ≡ (’1)n’1 ≡ (n ’ 1)n’1 ≡ 1 (mod n) .

Somit ist n ein Teiler von 2, d. h. n = 2. Aber n = 2 ist keine Carmichael-Zahl.

Satz 8.4
Es sei n eine ungerade zusammengesetzte natürliche Zahl. Gleichwertig sind:

(1) n ist eine Carmichael-Zahl.

(i) Aus p | n (für p ∈ P) folgt p ’ 1 | n ’ 1.
(2)
(ii) n ist quadratfrei (d. h., a2 | n für a ∈ N impliziert a = 1).

Beweis. (1) ’ (2): Es seien p ein Primteiler von n und ± ∈ N so gew¤hlt, dass
n = p± d mit p d. Nach Lemma 7.5 gilt Z — ∼ Z —± — Z — . Die Gruppe Z —± ist nach
n= p p
d
Satz 6.14 zyklisch (man beachte, dass n ungerade und somit p = 2 ist). Daher gibt
es in Z — ein Element a mit a ∈ {1, . . . , n ’ 1} und o(a) = •(p± ) = p±’1 (p ’ 1),
n
folglich gilt
±’1 (p’1)
≡ 1 (mod n) .
ap
8.3 Der Miller-Rabin-Test 147

Da ggT(a, n) = 1, gilt nach Voraussetzung

an’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-
mat. Wegen p ’ 1 | n ’ 1 gilt also auch an’1 ≡ 1 (mod p), d. h. p | an’1 ’ 1 für alle
p | n. Weil n quadratfrei ist, folgt hieraus n | an’1 ’ 1, d. h. an’1 ≡ 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 = p q mit Primzahlen p > q gilt. Wegen Satz 8.4
gilt
p ’ 1 | p q ’ 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 ’ (1/4)t .


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:

n ’ 1 = 2s d mit 2 d .
148 8 Primzahltests

Da n ungerade ist, gilt s ≥ 1.
Beim Fermat-Test haben wir ausgenutzt, dass für eine Primzahl n und jedes a ∈
{1, , . . . , n ’ 1} die Kongruenz an’1 ≡ 1 (mod n) erfüllt ist. Beim Miller-Rabin-
Test werden wir ausnutzen, dass für eine Primzahl die folgende Tatsache gilt:
Lemma 8.6
Es sei n eine Primzahl. Ist a ∈ {1, . . . , n ’ 1}, so gilt entweder

(i) ad ≡ 1 (mod n) oder
r
(ii) ≡ ’1 (mod n) für ein r ∈ {0, . . . , s ’ 1}.
a2 d


Beweis. Weil n eine Primzahl ist, gilt |Z — | = n ’ 1 = 2s d. Der Satz 6.9 von Euler
n
liefert (ad )2 = 1 in Z — . Wegen (iii) in Lemma 6.1 (b) ist o(ad ) ein Teiler von 2s . Es
s
n
gelte etwa o(ad ) = 2l mit l ∈ {0, . . . , s}.
1.Fall: l = 0: Dann gilt ad ≡ 1 (mod n), d. h., es gilt (i).
l’1
2.Fall: 0 < l ¤ s: Dann hat (ad )2 die Ordnung 2. Da ’1 das einzige Element
in Z — von der Ordnung 2 ist (das Polynom X 2 ’ 1 ∈ Z n [X] hat im Falle n ∈ P
n
l’1
nur ±1 als Nullstellen), gilt also in diesem Fall (ad )2 ≡ ’1 (mod n). Setze nun
r := l ’ 1. Damit gilt (ii).
Wegen dieses Lemmas können wir nun die folgende Aussage formulieren:

r
Gilt ad ≡ ±1 (mod n), a2 d ≡ ’1 (mod n)
für alle 1 ¤ r ¤ s ’ 1 und ein 1 < a < n,
so ist n garantiert zusammengesetzt.

Hiermit gewinnen wir den (probabilistischen) Miller-Rabin-Test:

W¤hle ein a ∈ {2, . . . , n ’ 1}.
s’1
Bestimme in Z n die s Potenzen ad , a2 d , . . . , a2 d
.

Gilt
s’1
ad = ±1, a2 d = ’1, . . . , a2 = ’1 ,
d


so ist n keine Primzahl, gib „n ∈ P“ aus.

Gilt
r
ad = ±1 oder a2 = ’1 für ein r ∈ {1, . . . , s ’ 1} ,
d


so ist n eventuell eine Primzahl, gib „n ∈ P“ aus (oder wiederhole das Verfah-
ren mit einem neuen a).

Wie beim Fermat-Test, ist es durchaus möglich, dass der Test „n ∈ P“ ausgibt,
obwohl n gar keine Primzahl ist. Gibt der Test aber „n ∈ P“ für viele verschiede-
ne a aus, so ist die Wahrscheinlichkeit dafür, dass n eine Primzahl ist, sehr groß.
8.3 Der Miller-Rabin-Test 149

Genauere Aussagen hierzu werden wir im Satz 8.7 machen. Auch hier erh¤lt man
mit a einen Zeugen für die Zusammengesetztheit von n, falls der Test „n ∈ P“
mit a ∈ {2, . . . , n ’ 1} ausgibt. Die Zahl a beweist, dass n keine Primzahl ist.

Bemerkung
s’1
Man beachte, dass man beim Miller-Rabin-Test die Elemente a2 d , . . . , a2 d
durch sukzessives Quadrieren aus dem Element ad erh¤lt.

Beispiel
Die Zahl 561 = 3 · 11 · 17 ist eine Carmichael-Zahl und damit problematisch für
den Fermat-Test. Wir wenden nun den Miller-Rabin-Test auf die Zahl 561 an.
Es gilt 561 ’ 1 = 24 · 35, also s = 4 und d = 35. In Z561 gilt

22 ·35 23 ·35
35 2·35
= 263 , = 166 , = 67 , = 1.
2 2 2 2

Damit ist gezeigt, dass 561 keine Primzahl ist. Die Basis a = 2 ist ein Zeuge für
die Zusammengesetztheit von 561.

Wir kümmern uns nun um die Zahlen n, für die der Miller-Rabin-Test das Ergeb-
nis „n ∈ P“ ausgibt. Unser Ziel ist eine Absch¤tzung für die Wahrscheinlichkeit,
dass der Test „n ∈ P“ ausgibt, obwohl n gar keine Primzahl ist.


8.3.2 Starke Pseudoprimzahlen
Eine natürliche Zahl n ∈ N heißt starke Pseudoprimzahl zur Basis a ∈
{1, . . . , n ’ 1}, wenn
r
ad = ±1 oder a2 = ’1 für ein r ∈ {1, . . . , s ’ 1}
d


erfüllt ist. Wir können die starken Pseudoprimzahlen auch wie folgt beschreiben:
Es sind dies jene Zahlen n, für die der Rabin-Miller-Test „n ∈ P“ ausgibt (unge-
achtet dessen, ob dieses Ergebnis korrekt ist oder nicht). Nach Lemma 8.6 ist jede
Primzahl n eine starke Pseudoprimzahl zu jeder Basis a mit 1 ¤ a ¤ n ’ 1. Es
folgt ein Beispiel einer starken Pseudoprimzahl, die keine Primzahl ist.

Beispiel
Wegen
85
341 ’ 1 = 22 · 85 und 4785 ≡ 1 (mod 341) , d. h. 47 =1
ist 341 (= 11 · 31) eine starke Pseudoprimzahl zur Basis 47.

Die Güte des Miller-Rabin-Tests beruht auf der Tatsache, dass es nur wenige star-
ke Pseudoprimzahlen gibt, die keine Primzahlen sind. Bevor wir das beweisen,
erinnern wir an den aus der linearen Algebra bekannten Homomorphiesatz der
Gruppentheorie, den wir für den Beweis benötigen:
150 8 Primzahltests

Der Homomorphiesatz. Ist • : G ’ H ein surjektiver Homomorphismus von der
Gruppe G auf die Gruppe H, so gilt

G/ ker • ∼ H .
=

Nun zu dem angekündigten Satz:

Satz 8.7
Es sei n eine ungerade zusammengesetzte natürliche Zahl. Weiter sei

A := {a ∈ {1, . . . , n ’ 1} ; n ist starke Pseudoprimzahl zur Basis a} .

n’1
|A| ¤
Dann gilt: .
4

Beweis. In A existiert auf jeden Fall ein Element a, das eine Kongruenz der Art
r
≡ ’1 (mod n) für ein r ∈ {0, . . . , s ’ 1}
a2 d


erfüllt, da n¤mlich im Falle ad ≡ 1 (mod n) auch die Kongruenz (’a)d ≡
’1 (mod n) gilt “ man beachte, dass d ungerade ist.
k
Es sei k ∈ {0, . . . , s ’ 1} die größte Zahl mit der Eigenschaft a2 d ≡ ’1 (mod n)
für ein a ∈ A. Es gilt dann für alle a ∈ A:
k
(—) a2 ≡ ±1 (mod n) .
d

ν
ν
Wir betrachten die folgenden Untergruppen von Z — , dabei seien n = p11 · · · p
n
die kanonische Primfaktorzerlegung von n und m := 2k d (beachte, dass wegen
k < s die Zahl m ein echter Teiler von n ’ 1 = 2s d ist):

J = {a ∈ Z — ; an’1 ≡ 1 (mod n)} ,
n
ν
K = a ∈ Z — ; am ≡ ±1 (mod pi i ) für alle i ∈ {1, . . . , } ,
n
L = a ∈ Z — ; am ≡ ±1 (mod n) ,
n
M = a ∈ Z — ; am ≡ 1 (mod n) .
n

Offenbar gelten die Inklusionen A ⊆ L (vgl. (—)) und M ⊆ L ⊆ K ⊆ J ⊆ Z — . Im
n
Folgenden begründen wir |L| ¤ 4 , hieraus folgt dann die Behauptung.
n’1

Nach Lemma 7.5 dürfen wir Z — mit Z —ν1 — · · · — Z —ν identi¬zieren. Für die Po-
n p1 p
Z —ν1 — · · · — Z —ν gilt dann:
tenzabbildung πm : a ’ a , m = m
2k d, in
p1 p

’1 ’1
M = ker πm , L = πm ({±(1, . . . , 1)}) , K = πm ({(±1, . . . , ±1)}) .

Wir begründen nun die beiden Aussagen:
(1) |L| = 2 |M| und
(2) |K| = 2 |M|.
8.3 Der Miller-Rabin-Test 151

Zu (1): Der Homomorphismus πm | L : L ’ {±(1, . . . , 1)} ist wegen der Wahl von
k surjektiv. Mit dem Homomorphiesatz folgt L/M ∼ {±(1, . . . , 1)}, insbesonde-
=
re |L|/|M| = |{±(1, . . . , 1)}| = 2, und das ist die Behauptung (1).
Zu (2): Wir betrachten den Homomorphismus πm |K : K ’ {(±1, . . . , ±1)} und
zeigen, dass dieser surjektiv ist. Es folgt dann erneut mit dem Homomorphiesatz
K/M ∼ {(±1, . . . , ±1)}, insbesondere |K|/|M| = |{(±1, . . . , ±1)}| = 2 , und
=
das ist die Behauptung (2).
Es sei (c1 , . . . , c ) ∈ {(±1, . . . , ±1)} vorgegeben. Wir w¤hlen Mengen I und I
mit ci = 1 für alle i ∈ I und c j = ’1 für alle j ∈ I und I ∪ I = {1, . . . , }. Nach
der Wahl von m gibt es ein a ∈ A mit am ≡ ’1 (mod n). Nach dem chinesischen
Restsatz 7.4 hat das Kongruenzgleichungssystem
νj
ν
X ≡ 1 (mod pi i ) , i ∈ I und X ≡ a (mod p j ) , j ∈ I

eine Lösung c ∈ Z. Das Element c ∈ Z n liegt in K. Wir interpretieren c als Element
in Z —ν1 — · · · Z —ν . Dann gilt πm (c) = (c1 , . . . , c ). Folglich ist πm |K surjektiv. Es
p1 p
ist hiermit (2) begründet.
Mit (1) und (2) erhalten wir die Absch¤tzung:

<< . .

. 19
( : 33)



. . >>