<<

. 6
( 9)



>>


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:

|K| n’1
|A| ¤ |L| = ¤ ’1 .
2 ’1 2
Wir treffen Fallunterscheidungen für .
1. Fall: ≥ 3: Dann gilt |L| ¤ n’1 , wie gewünscht.
4
νν
2. Fall: = 2: Dann gilt n = p11 p22 . Nach Korollar 8.5 ist n keine Carmichael-
Zahl, sodass J = Z — gilt. Also gilt 2 ¤ |Z — /J| = |Z — |/|J| = •(n)/|J|, und
n n n
damit (beachte (1) und (2)):
•(n) |J| |K|
•(n) = |L| ≥ 2 · 1 · 2 · |L| .
|J| |K| |L|
•(n)
Folglich gilt |L| ¤ 4 ¤ n’1 , wie gewünscht.
4
3. Fall: = 1: Es gilt n = pν , ν ≥ 2. Wegen •(n) = pν’1 (p ’ 1) ist p ein Teiler
von •(n). Nach dem Satz 6.8 von Cauchy existiert ein a ∈ Z — mit o(a) = p, d. h.
n
a p = 1. Da p n ’ 1, gilt an’1 = 1, sodass a ∈ J, also {J, a J, . . . , a p’1 J} ⊆ Z — /J.
n
— /J| ≥ p, also |J| ¤ •(n) .
Damit gilt |Z n p
Im Fall p > 3 erhalten wir hieraus das Gewünschte aus |L| ¤ |J| unmittelbar. Es
bleibt der Fall p = 3 zu untersuchen: Es sei n = 3ν mit ν ≥ 2.
Falls ν = 2 ist, ist n = 9 und damit s = 3 und d = 1. Wegen 8 ≡ ’1 (mod 9)
ist 9 eine starke Pseudoprimzahl zur Basis 8, d. h. {1, 8} ⊆ A. Und tats¤chlich
gilt {1, 8} = A, da für alle weiteren a zwischen 1 und 9 gilt a ≡ ±1 (mod 9),
a2 ≡ ’1 (mod 9), a4 ≡ ’1 (mod 9). Es folgt |A| = 2 ¤ 9’1 , wie gewünscht.
4
Nun zum letzten Fall p = 3 und ν > 2: Es gilt o(4)mod33 = 9. Daher gilt auch
o(4)mod3ν ≥ 9, da aus 4r ≡ 1 (mod 3ν ) für r < 9 auch 4r ≡ 1 (mod 33 ) folgte.

Wegen |Z3ν | = •(3ν ) = 2 · 3ν’1 gilt o(4)mod3ν | 2 · 3ν’1 . Da, wie bereits gezeigt
152 8 Primzahltests

o(4)mod3ν ≥ 9 gilt, können wir sagen, dass 3 ein Teiler von o(4)mod3ν ist. Und
weil n ’ 1 = 3ν ’ 1 sicher nicht von 3 geteilt wird, erhalten wir für das Element
4 ∈ Z — sogar 4 ∈ J, da 4n’1 ≡ 1 (mod 3ν ).
n
Wir betrachten nun die Faktorgruppe Z — /J. Diese Gruppe enth¤lt mindestens
n
•(n)
8
die neun verschiedenen Elemente J, 4 J, . . . , 4 J. Damit gilt |J| ¤ 9, wegen
|L| ¤ |J| erhalten wir wieder das Gewünschte.
Wir interpretieren das Ergebnis aus Satz 8.7: Liefert der Miller-Rabin-Test „n ∈
P“ für eine Basis a ∈ {2, . . . , n ’ 1}, so ist die untersuchte ungerade natürliche
Zahl n mit einer Wahrscheinlichkeit kleiner gleich 1 dennoch zusammengesetzt.
4
Nach zehn solchen positiven Tests mit zehn verschiedenen a ist n mit einer Wahr-
scheinlichkeit von kleiner gleich (1/4)10 ≈ 10’6 zusammengesetzt, allgemeiner:

Korollar 8.8
Die Wahrscheinlichkeit dafür, dass n zusammengesetzt ist, obwohl der Miller-Rabin-Test
„n ∈ P“ mit t verschiedenen, zuf¤llig gew¤hlte a ausgibt, ist kleiner als (1/4)t .


Bemerkung
Der Miller-Rabin-Test ist das Mittel der Wahl, um Primzahlen von der Größen-
ordnung 512 Bit, wie sie beim RSA-Verfahren benutzt werden, zu erzeugen.



Der AKS-Test *
8.4
Der AKS-Primzahltest wurde 2002 von Agrawal, Kayal und Saxena veröffent-
licht. N. Kayal und N. Saxena waren damals Studenten. Es handelt sich um den
ersten deterministischen Primzahltest mit polynomialer Laufzeit. Die Veröffent-
lichung war daher eine Sensation. Die Korrektheit des Algorithmus “ an der un-
mittelbar nach der Veröffentlichung verschiedentlich gezweifelt wurde “ wurde
in nur wenigen Tagen von bedeutenden Mathematikern best¤tigt. Das wohl Er-
staunlichste am AKS-Test ist, dass er mit nur wenigen Vorbereitungen von jedem
Mathematikstudenten verstanden werden kann, obwohl Fachleute schon lange
erfolglos nach einem solchen Test gesucht haben.
In diesem Abschnitt sei n ∈ N >1 , und := log2 n + 1 sei die L¤nge von n in
Bin¤rdarstellung. Diese Zahl n wollen wir auf Primalit¤t prüfen.


8.4.1 Ideale in Ringen

Unter einem Ideal eines kommutativen Ringes R versteht man eine Untergruppe
I von (R, +) mit der Eigenschaft I R ⊆ I, d. h.:

a ∈ I, r ∈ R ’ ar ∈ I.
8.4 Der AKS-Test * 153

Im Rahmen des AKS-Testes werden uns Ideale in Polynomringen interessieren.
Dazu erinnern wir an den Polynomring K[X] über einem Ring K, insbesondere
über Z:
k
‘ ai X i ;
f= k ∈ N0 , ai ∈ K für alle i = 0, . . . , k
K[X] := .
i=0

Polynomringe wurden im Abschnitt 3.1.2 eingeführt. Nachfolgend die für alles
weitere wesentlichen Beispiele für Ideale.

Beispiel
Für jedes Element a eines kommutativen Ringes R ist
I = (a) := a R = {a r ∈ R ; r ∈ R}
ein Ideal.
Etwas allgemeiner: Für beliebige Elemente a1 , . . . , ak eines kommutativen Rin-
ges R bildet
I = (a1 , . . . , ak ) := a1 R + · · · + ak R = {a1 r1 + · · · + ak rk ; r1 , . . . , rk ∈ R}
ein Ideal von R “ man nennt es das von a1 , . . . , ak erzeugte Ideal von R.
{0} und R sind Ideale von R “ die sogenannten trivialen Ideale des Ringes R,
man nennt {0} das Nullideal und R das Einsideal von R; es gilt {0} = (0)
und R = (1).
Die Ideale von Z sind genau die Mengen (k) = k Z mit k ∈ N0 . Den Nachweis
dieser Aussage haben wir als Übungsaufgabe gestellt.
Für jedes f ∈ Z[X] ist I = ( f ) = f Z[X] = { f g ; g ∈ Z[X]} ein Ideal des
Polynomrings Z[X] “ dies ist ein Sonderfall des ersten Beispiels.

Wir treffen eine Vereinbarung: Wir schreiben für ein Ideal I eines Ringes R und
Elemente r, s ∈ R
r ≡ s (mod I) :” r ’ s ∈ I
und sagen in diesem Fall, dass r und s kongruent modulo I sind. Diese Schreib-
weise kollidiert nicht mit der bereits vielfach benutzten Schreibweise
a ≡ b (mod k) ” k | a ’ b
für ganze Zahlen a und b. Es gilt n¤mlich:
a ≡ b (mod (k)) ” a ’ b ∈ (k) = k Z ” k | a ’ b ” a ≡ b (mod k) .

Beispiel
Für den kommutativen Ring Z[X] und I = (k) = k Z[X], k ∈ N, gilt etwa
X 3 ’ k X ≡ X 3 (mod I) ,
da die Differenz (X 3 ’ k X) ’ X 3 in I liegt.
154 8 Primzahltests

8.4.2 Die Idee des AKS-Tests

Sowohl beim Fermat-Test wie auch beim Miller-Rabin-Test sind wir von einer
Eigenschaft von Primzahlen ausgegangen:
Wenn n eine Primzahl ist, dann gelten ... gewisse Kongruenzen.
Der Test selbst verl¤uft dann dergestalt, dass man diese Kongruenzen einfach
nachprüft: Sind die Kongruenzen erfüllt, so gibt der Test „n ∈ P“ aus, und das ist
ein Hinweis darauf, dass die untersuchte Zahl eine Primzahl sein könnte. Sind die
Kongruenzen nicht erfüllt, so gibt der Test „n ∈ P“ aus, und das ist ein Beweis,
dass die untersuchte Zahl keine Primzahl ist.
Beim AKS-Test werden wir dieses Prinzip wieder¬nden. Wir zeigen:
Wenn n eine Primzahl ist, dann gilt eine ... noch n¤her zu bestimmende Kongruenz.
Aber es gibt einen wesentlichen Unterschied zum Fermat- und Miller-Rabin-Test:
Liefert der AKS-Test das Ergebnis „n ∈ P“ oder „n ∈ P“ so ist das nicht nur ein
Hinweis, es ist sogar ein Beweis für diese Aussage. Der AKS-Test ist also determi-
nistisch.
Es seien n ∈ N eine Primzahl und a ∈ Z. Mit der Binomialformel erhalten wir:
n
n n n

(X + a) = ai X n’i = X n + a X n’1 + · · · + an’1 X + an .
n
n’1
1
i
i=0

Und nun rechnen wir im Polynomring Z[X] modulo dem Ideal I = (n), d. h., wir
lassen einfach alle Summanden von (X + a)n weg, die Vielfache von n in Z[X]
sind, und erhalten:
(X + a)n ≡ X n + an (mod (n)) .
Beachtet man jetzt noch den Satz 6.10 von Fermat, so können wir hierin an durch
a ersetzen, da n eine Primzahl ist. Damit ist bereits die Richtung ’ des folgenden
Lemmas bewiesen:

Lemma 8.9
Gegeben seien zwei teilerfremde natürliche Zahlen a und n. Die Zahl n ist genau dann
eine Primzahl, wenn im Ring Z[X] gilt
(X + a)n ≡ X n + a (mod (n)) .

Beweis. Wir begründen ⇐: Angenommen, n ist keine Primzahl. Dann sei pk die
maximale Potenz eines (echten) Primteilers p von n, d. h. n = pk r für eine Prim-
zahl p und natürliche Zahlen k und r und p r. Wir betrachten den Binomialko-
ef¬zienten
n (n ’ 1) · · · (n ’ p + 1)
n
= ∈ N.
p (p ’ 1) · · · 1
p
In dem rechten Bruch kürzt sich das p im Nenner mit einem entsprechenden
Faktor von n des Z¤hlers, da die Faktoren n ’ 1, . . . , n ’ p + 1 des Z¤hlers zu p
teilerfremd sind, es gilt n¤mlich
n ’ i ≡ ’i ≡ 0 (mod p) für i = 1, . . . , p ’ 1 .
8.4 Der AKS-Test * 155

n
Damit ist aber pk kein Teiler von . Es folgt wegen p a:
p

np
n
a ≡ 0 (mod (n)) .
pk a p und somit
p p
Und hieraus folgt mit der Binomialformel ein Widerspruch:
n
(X + a)n ’ X n ’ a ≡ · · · + a p X n’p + · · · ≡ 0 (mod (n)) ,
p

n
es hat n¤mlich das in der Mitte stehende Polynom · · · + a p X n’p + · · · we-
p
gen p < n einen Summanden, der nicht Vielfaches von n ist.
Ist für n ∈ N zu entscheiden, ob n eine Primzahl ist, so w¤hle man ein a ∈ Z,
prüfe zun¤chst, ob ggT(a, n) = 1, und teste dann, ob die Kongruenz
(X + a)n ≡ X n + a (mod (n))
erfüllt ist. Falls nicht, so ist n garantiert keine Primzahl. Gilt diese Kongruenz
hingegen, so ist n garantiert eine Primzahl.
Aber in dieser Form ist der Test viel zu rechenaufw¤ndig. Tats¤chlich sind im All-
gemeinen alle Koef¬zienten von (X + a)n modulo (n) zu bestimmen, was einen
exponentiellen Aufwand bedeutet. Die Laufzeit des AKS-Tests aber ist polynomi-
al. Diesen polynomialen Aufwand erreichen wir dadurch, dass wir nicht modulo
dem Ideal (n) in Z[X], sondern modulo dem von n und X r ’ 1 in Z[X] erzeugten
Ideal I = (n, X r ’ 1) rechnen. Die Zahl r ∈ N ist dabei noch n¤her zu bestimmen.
Zuerst halten wir fest: Ist n ∈ N eine Primzahl, so gilt für jedes r ∈ N und jedes
a ∈ Z auch die Kongruenz
(—) (X + a)n ≡ X n + a (mod I) .
Diese Kongruenz kann mit der schnellen Exponentiation ausgewertet werden.
Dabei wird die Laufzeit von r und log n bestimmt. In der Tat gilt folgende grobe
Absch¤tzung.

Lemma 8.10
Die Laufzeit zur Auswertung von (—) ist asymptotisch beschr¤nkt durch O (r · log n)3 .

Beweis. Nach Lemma 6.15 kann die n-te Potenz in O(log n) Operationen des Rin-
ges Z n [X]/(X r ’ 1) durchgeführt werden. Dazu wird in jedem Schritt eine Di-
vision mit Rest nach X r ’ 1 durchgeführt, und anschließend werden alle r + 1
Koef¬zienten des Ergebnisses modulo n reduziert. Mit den Lemmata 4.5 und 4.7
erhalten wir
O(log n) · O(r2 ) · (r + 1) O (log n)2 = O (r log n)3 ,

wie behauptet.
156 8 Primzahltests

Nun taucht ein anderes Problem auf: W¤hrend im Lemma 8.9 „genau dann,
wenn“ steht, haben wir nun wieder nur eine „Wenn ..., dann ...“-Beziehung: Die
Kongruenz (—) kann auch dann für Zahlen a und r erfüllt sein, wenn n keine
Primzahl ist. Ein entsprechender Test scheint also doch wieder probabilistisch zu
sein. Wir werden jedoch zeigen, dass es im Fall, dass n keine Primzahl ist, stets
ein a gibt, sodass die Kongruenz (—) nicht erfüllbar ist.
Der Knackpunkt des AKS-Tests besteht darin, dass es genügt, die Kongruenzglei-
chung (—) für ein kleines r und einen kleinen Bereich für a zu prüfen.
Die Tatsache, dass wir r und die Anzahl der Auswertungen von (—) beschr¤nken
können, bewirkt, dass der Algorithmus polynomial ist.


8.4.3 Der AKS-Algorithmus

Wir formulieren zuerst den AKS-Algorithmus und zeigen dann, dass der Algo-
rithmus das gewünschte Ergebnis liefert.
Eingabe: n ∈ N >1 der L¤nge = log2 n + 1.
Ausgabe: „n ∈ P“ oder „n ∈ P“.

Teste, ob n eine (echte) Potenz ist (vgl. Aufgabe 8.6). Falls ja, so gib „n ∈ P“
(1)
aus, sonst fahre fort mit:

Finde r ∈ N minimal mit o(n)mod r > 2.
(2)

Teste n auf Primteiler p ¤ 5. Falls ein solcher existiert, so gib aus
(3)

„n ∈ P“, falls p = n,
„n ∈ P“, sonst.

Andernfalls fahre fort mit:

Für a = 1, 2, . . . , r prüfe:
(4)
Falls (X + a)n ≡ X n + a (mod (n, X r ’ 1)), so gib „n ∈ P“ aus, sonst:

Gib „n ∈ P“ aus.
(5)

Bevor wir die Korrektheit des Algorithmus beweisen, zeigen wir, dass im Schritt
(2) des Algorithmus die Absch¤tzung

r¤ 5


gilt, sodass also r tats¤chlich klein ist. Für die Begründung benötigen wir das fol-
gende Lemma:

Lemma 8.11
Für n ∈ N sei »(n) := kgV(1, 2, . . . , n). Dann gilt »(n) ≥ 2n’2 .
8.4 Der AKS-Test * 157

Beweis. Für ein N ∈ N betrachten wir das Polynom f = a2N X 2N + · · · + a1 X +
a0 X 0 ∈ Z[X]. Es gilt

2N 2N
1 1 a m
‘ ai ‘ i +i 1 =
f (t) d t = t dt = für ein m ∈ Z .
i
»(2 N + 1)
0 0
i=0 i=0

Nun betrachten wir das spezielle Polynom f = X N (1 ’ X) N , das eine sol-
che betrachtete Form hat. Es gilt für alle 0 < t < 1 die Ungleichungskette
0 < f (t) ¤ 41 “ für die Absch¤tzung nach oben zeige man, dass die Polynom-
N

funktion f (x) = (x (1 ’ x)) N auf dem Intervall [0, 1] ein globales Maximum in
x = 1/2 besitzt. Es folgt
1 1
m
0< f (t) d t = ¤N
»(2 N + 1) 4
0

für ein m ∈ N. Das liefert

»(2N + 1) ≥ 4 N ≥ 2(2N+1)’2 ,

also die Behauptung für ungerade n = 2 N + 1. Wegen

»(2 N + 2) ≥ »(2 N + 1) ≥ 4 N = 2(2N+2)’2

folgt die Behauptung auch für gerade n = 2 N + 2.

Mit diesem Lemma können wir nun zeigen, dass es ein r der gewünschten Grö-
ßenordnung gibt.

Lemma 8.12
Zu n ∈ N >1 der L¤nge = log2 n + 1 mit ggT(n, »( 5 )) = 1 existiert ein r ∈ N
mit r ¤ 5 und o(n)mod r > 2 .

Beweis. Wir nehmen an, dass kein solches r existiert. Dann gilt o(n)mod r ¤ 2 für
jedes r ¤ 5 , denn r und n sind nach Voraussetzung teilerfremd. Das besagt, dass
für jedes r ¤ 5 eine Kongruenz der Form ni ≡ 1 (mod r) für ein i ∈ {1, . . . , 2 }
gilt. Damit erhalten wir für jedes r ¤ 5 :
2 2

∏(n ’ 1) und damit »( ) | ∏(ni ’ 1) .
r| 5
i
i=1 i=1

5 ’2
Wir wenden nun Lemma 8.11 an, wonach »( 5 ) ≥ 2 gilt; wir erhalten:
2 2
( 2 +1)/2
2
5 ’2 ( 2 +1)/2 log2 (n) ( 2 +1)/2
2 3
¤ ∏(n ’ 1) < ∏ n = n =2 ¤2
i i
2 .
i=1 i=1
158 8 Primzahltests

Ein Vergleich der Exponenten liefert
’4 < + ( ’ 1) < 4 .
5 5 3 3 2
2 und damit
Wegen n > 1 ist aber > 1. Damit haben wir einen Widerspruch gefunden, es
muss also ein r ¤ 5 mit o(n)mod r > 2 existieren.
Aus diesen Überlegungen ergibt sich:

Korollar 8.13
Der AKS-Algorithmus ist polynomial.


8.4.4 Introspektive Zahlen

Zum Beweis der Korrektheit des AKS-Algorithmus benutzen wir eine Eigen-
schaft sogenannter introspektiver Zahlen. Ist p eine Primzahl, so heißt eine na-
türliche Zahl m introspektiv für ein f ∈ Z p [X] und r ∈ N, falls
f (X)m ≡ f (X m ) (mod (X r ’ 1)) .

Beispiel
Die Zahl m = 2 ist introspektiv für f = X + 1 ∈ Z2 [X] und jedes r ∈ N, da gilt
(X + 1)2 ≡ X 2 + 1 (mod (X r ’ 1)) .
Lemma 8.14
Es seien p ∈ P eine Primzahl und r ∈ N eine natürliche Zahl. Dann gilt:
Sind m, m introspektiv für ein f ∈ Z p [X] und r ∈ N, so ist auch m m intro-
(a)
spektiv für f und r ∈ N.
Ist m introspektiv für f , g ∈ Z p [X] und r ∈ N, so ist m auch introspektiv für f g
(b)
und r ∈ N.

Beweis. (a) Es seien m, m introspektiv für f ∈ Z p [X] und ein r ∈ N. Wir erhalten
dann:
f (X)mm ≡ f (X m )m (mod (X r ’ 1)) .
Da m introspektiv für f und r ist, gilt auch

f (X m )m ≡ f (X mm ) (mod (X mr ’ 1)) .
Hieraus folgt
f (X m )m ≡ f (X mm ) (mod (X r ’ 1)) ,
da X r ’ 1 | X mr ’ 1 gilt. Das besagt, dass m m introspektiv für f und r ist.
(b) Es gilt
( f g)(X)m ≡ f (X)m g(X)m ≡ f (X m ) g(X m ) ≡ ( f g)(X m ) (mod (X r ’ 1)) .
Das besagt, dass m introspektiv für f g und r ist.
8.4 Der AKS-Test * 159

Um weitere Aussagen über introspektive Zahlen zu gewinnen, benötigen wir die
folgende Aussage.

Lemma 8.15
Es sei f ∈ K[X] ein Polynom über einem Körper K. Ist X r ’ 1 ein Teiler von f p , p ∈ N,
so teilt X r ’ 1 bereits f , d. h.

Xr ’ 1 | f p ’ Xr ’ 1 | f .

Beweis. Angenommen, es ist g ∈ K[X] mit deg g > 0 ein Teiler von X r ’ 1, d. h.

X r ’ 1 = gs h mit einem h ∈ K[X] .

Wir leiten die Polynome nach X ab und erhalten mit der Produktregel für die
Ableitung:
r X r’1 = s gs’1 g h + gs h .

W¤re s > 1, so h¤tten wir in g einen gemeinsamen Teiler von X r ’ 1 und seiner
Ableitung rX r’1 gefunden. Ein solcher gemeinsamer Teiler w¤re aber auch ein
Teiler der Differenz ’1 dieser Polynome. Folglich muss s = 1 gelten: Jeder Teiler
g von X r ’ 1 mit deg g > 0 kommt in einfacher Potenz vor, d. h. X r ’ 1 = h1 · · · ht
mit verschiedenen irreduziblen Polynomen h1 , . . . , ht .
Für jedes dieser hi gilt hi | f , wie mehrfaches Anwenden von Lemma 3.7 zeigt.
Induktiv folgt f = h1 . . . ht f t = (X r ’ 1) f t für ein Polynom f t ∈ K[X], wie be-
hauptet.

Nun haben wir alle Zutaten, um das folgende Ergebnis über introspektiven Zah-
len begründen zu können. Wir werden es benötigen, um die Korrektheit des AKS-
Algorithmus zu zeigen.

Lemma 8.16
Es sei k ∈ N, und p sei ein Primteiler der natürlichen Zahl n. Falls für jedes a ∈
{0, 1, . . . , k} die Kongruenz

(X + a)n ≡ X n + a (mod (n, X r ’ 1))

gilt, so sind alle Elemente der Menge

t
n
; s, t ∈ N0
s
J := p
p

k
introspektiv für jedes Polynom f ∈ Q := ∏ (X + a)ea ; ea ∈ N0 ⊆ Z p [X] und
a=0
r ∈ N.
160 8 Primzahltests

Beweis. Wir zeigen, dass p und n introspektiv für jedes X + a ∈ Z p [X] und r ∈ N
p
sind. Da nach Lemma 8.14 (a) beliebige Produkte introspektiver Zahlen wieder
introspektiv sind, folgt hieraus die Behauptung für jedes Polynom der Form f =
X + a, a ∈ {0, 1, . . . , k}. Mit der Aussage (b) in Lemma 8.14 folgt dann schließlich
die Behauptung für alle f ∈ Q. Wegen

(X + a)n ≡ X n + a (mod (n, X r ’ 1)) für alle a ∈ {0, 1, . . . , k}
gilt auch

(X + a)n ≡ X n + a (mod (p, X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Nach Lemma 8.9 gilt (X + a) p ≡ X p + a (mod (p)) für alle betrachteten a (für
die Richtung ’ in Lemma 8.9 war die Einschr¤nkung ggT(a, n) = 1 nicht nötig),
also gilt auch

(X + a) p ≡ X p + a (mod (p, X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Diese Kongruenz besagt, dass es Polynome f , g ∈ Z[X] mit

(X + a) p ’ (X p + a) = p f + (X r ’ 1) g
gibt. Wir fassen diese Kongruenz nun als Kongruenz über Z p [X] auf, indem wir
modulo p rechnen. Wir ersetzen also a, 1, p ∈ Z der Reihe nach durch a, 1, p =
0 ∈ Z p . Es folgt

(X + a) p ≡ X p + a (mod (X r ’ 1)) für alle a ∈ {0, 1, . . . , k} .
Daher ist p introspektiv für X + a, a ∈ {0, 1, . . . , k}, und alle r ∈ N.
Weiterhin erhalten wir für alle a ∈ {0, 1, . . . , k}:
n ·p n ·p n
(X + a) p ≡ (X + a)n ≡ (X n + a) ≡ X p + a ≡ (X p + a) p (mod (p, X r ’ 1)) .
·p
n n
Um diese letzte Kongruenz X p + a ≡ (X p + a) p (mod (p, X r ’ 1)) einzusehen,
gehe man wie im Beweis von ’ zu Lemma 8.9 vor. Wir wenden diesen Trick
·p
n
mit der Binomialformel erneut an und erhalten aus der Kongruenz (X + a) p ≡
n
(X + a) p (mod (p, X r ’ 1)) nun
p

p
n n
(X + a) p ’ (X p + a) ≡ 0 (mod (p, X r ’ 1)) .

Modulo p gerechnet, besagt diese letzte Kongruenz, dass das Polynom X r ’ 1 ∈
p
n n
Z p [X] ein Teiler des Polynoms (X + a) p ’ (X p + a) ∈ Z p [X] ist. Und nun
kommt Lemma 8.15 ins Spiel, es gilt:
n n
(X + a) p ≡ (X p + a) (mod (X r ’ 1)) .
Somit ist also auch n introspektiv für alle X + a, a ∈ {0, 1, . . . , k}, und r ∈ N.
p
Nun beachte man die Aussagen (a) und (b) in Lemma 8.14.
8.4 Der AKS-Test * 161

8.4.5 Die Korrektheit des AKS-Algorithmus

Im Folgenden benutzen wir die Nummerierung (1) “ (5) der Schritte im AKS-
Algorithmus auf Seite 156. Wir begründen die Korrektheit des Algorithmus, in-
dem wir zeigen:

Satz 8.17
Es ist n genau dann eine Primzahl, wenn der AKS-Algorithmus „n ∈ P“ ausgibt.

Beweis. ’: Ist n eine Primzahl, so terminiert der Algorithmus im Schritt (5).
⇐: Der Algorithmus ende bei (5). Wir führen den Beweis in mehreren Schritten.
(i) Es existiert ein Primteiler p von n mit p ≡ 1 (mod r) und p > r.
Würde n¤mlich für jeden Primteiler p von n die Kongruenz p ≡ 1 (mod r) gel-
ten, so würde im Widerspruch zu (2) auch n ≡ 1 (mod r) gelten. Aufgrund von
Schritt (3) und Lemma 8.12 gilt p > r. Damit ist (i) begründet.
Wir werden in den n¤chsten Schritten zeigen, dass n außer p keinen weiteren
Primteiler besitzt. Nach Schritt (1) des Algorithmus ist dann n = p; so folgt also
die Behauptung. Dazu begründen wir zun¤chst:

⊆ Zr gilt < |G| < r.
n 2
(ii) Für die Gruppe G := p, p
Man beachte zun¤chst, dass wegen Schritt (2) im Algorithmus die Zahlen p und

p beide zu r teilerfremd sind, sodass p, p ∈ Z r gilt. Da G eine Untergruppe von
n n

Zr ist (vgl. die Bemerkung auf Seite 96), gilt natürlich |G| < r. Das Element n =
p n liegt in G. Folglich liegen auch alle Potenzen von n in G, d. h. n ⊆ G. Wegen
p
o(n)mod r > 2 (siehe Schritt (2) im AKS-Algorithmus) folgt die Ungleichung <
2

|G|. Damit ist (ii) begründet.
— —
Nach (i) gilt p = 1 ∈ Zr . Da Zr eine endliche Gruppe ist, existiert nach Lemma
6.1 ein s ∈ N mit ps = 1, d. h. ps ≡ 1 (mod r). Wir setzen q := ps und erhalten

r | q ’1.

Wir betrachten nun den endlichen Körper F q mit genau q Elementen (siehe Satz
3.10), wegen q = ps enth¤lt F q den Körper Z p . Die multiplikative Gruppe F — des
q
endlichen Körpers F q ist nach Lemma 6.12 zyklisch. Die Ordnung dieser (end-
lichen) zyklischen Gruppe F — ist q ’ 1. Da r ein Teiler von q ’ 1 ist, existiert
q
nach Lemma 6.6 ein Element ξ ∈ F — mit der Ordnung r. Im Folgenden spielt die
q
Gruppe

H := {ξ + a ; a = 0, . . . , k} = ξ, ξ + 1, . . . , ξ + k ⊆ F — mit k := r
q

eine entscheidende Rolle. Wir zeigen:
|G| + k
(iii) Es gilt |H| ≥ für G aus (ii).
k+1
162 8 Primzahltests

Zur Begründung von (iii) betrachten wir die Menge

k
∏ (X + a)ea ;
f= ea ∈ N0 , deg f < |G| ⊆ Z p [X] .
P :=
a=0

Man beachte, dass f (ξ) ∈ H für jedes f ∈ P. Wir begründen, dass die Abbildung

¦ : P ’ H , f ’ f (ξ)

injektiv ist, es folgt dann |P| ¤ |H|: Es seien f 1 , f 2 ∈ P mit f 1 (ξ) = f 2 (ξ) gew¤hlt.
Nach (4) des AKS-Algorithmus sind wegen Lemma 8.16 die Zahlen m = ps ( n )t p
mit ganzen Zahlen s, t ≥ 0 introspektiv für f i und r. Wir erhalten damit

f i (X)m ≡ f i (X m ) (mod (X r ’ 1)) , d. h. f i (X)m ’ f i (X m ) = g (X r ’ 1)

für ein g ∈ Z[X]. Wir setzen ξ in X ein und beachten o(ξ) = r, d. h. ξ r ’ 1 = 0:

(—) f 1 (ξ m ) = f 1 (ξ)m = f 2 (ξ)m = f 2 (ξ m ) .

Somit ist ξ m eine Nullstelle des Polynoms f 1 ’ f 2 . Wir begründen nun, dass das
Polynom f 1 ’ f 2 vom Grad < |G| mindestens |G| verschiedene Nullstellen im
Körper F q besitzt. Damit kann f 1 ’ f 2 nur das Nullpolynom sein, d. h. f 1 = f 2 ,
und damit ist die Injektivit¤t von ¦ gezeigt.
Es seien a und b verschiedene Elemente aus G:
t v
n n —
a= , b= ∈ Zr .
ps pu
p p

Ohne Einschr¤nkung seien a und b die kleinsten positiven Repr¤sentanten der
Nebenklassen a und b. Da a und b verschieden und kleiner als die Ordnung r von
ξ sind, gilt
ps ( n )t pu ( n )v
= ξa = ξb = ξ
ξ .
p p


Folglich sind ξ a und ξ b verschiedene Nullstellen von f 1 ’ f 2 . Daher hat das Po-
lynom f 1 ’ f 2 mindestens |G| viele Nullstellen, sodass ¦ injektiv ist. Bisher ist
gezeigt |H| ≥ |P|. Nun begründen wir

|G| + k
|P| = .
k+1

Aus k ¤ r < r < p (man beachte (i) und (ii)) folgt, dass die k + 1 Monome
X + a ∈ Z p [X] mit a ∈ {0, 1, . . . , k} verschieden sind. Folglich sind die beiden
Mengen P und T = (e0 , e1 , . . . , ek ) ∈ N0 ; ‘k ea < |G| gleichm¤chtig, so-
k+1
a=0
dass gilt
|H| ≥ |P| = |T| .
8.4 Der AKS-Test * 163

Wir zeigen nun noch
|G| + k
|T| = .
k+1
Hieraus folgt dann die Behauptung in (iii). Dazu ordnen wir jeder (k + 1)-
elementigen Teilmenge {x0 , x1 , . . . , xk } von {1, . . . , |G| + k} (wobei wir ohne Ein-
schr¤nkung x0 < x1 < · · · < xk setzen) ein Tupel (e0 , e1 , . . . , ek ) zu, indem wir
die ei aus den folgenden Gleichungen gewinnen:

e0 + 1 = x 0 , e0 + e1 + 2 = x 1 , . . . , e0 + e1 + · · · + e k + k + 1 = x k .

Da xk ¤ |G| + k, liegt das (k + 1)-Tupel (e0 , e1 , . . . , ek ) in der Menge T. Damit
haben wir eine Abbildung von der Menge aller (k + 1)-elementigen Teilmengen
von {1, . . . , |G| + k} in T erkl¤rt. Diese Abbildung ist offenbar bijektiv. Folglich
sind die beiden Mengen P und T gleichm¤chtig und (iii) ist begründet.
Als N¤chstes begründen wir:

(iv) |H| > n |G| .
In der folgenden Ungleichungskette beachte man der Reihe nach die Ungleichun-
gen bzw. Gleichungen |G| ≥ |G| + 1 (siehe (ii)), ( a+b ) = ( a+b ) für alle
a
b
a, b ∈ N, k ≥ |G| (siehe (ii)), ( 2a+1 ) > 2a+1 für alle a ∈ N >1 (siehe Aufga-
a
be 8.7) und schließlich = log2 n + 1:
⎛ ⎞
|G| + 1 + k
(iii) |G| + k |G| + 1 + k
=⎝ ⎠
|H| ≥ ≥
k+1 |G|
k+1
⎛ ⎞
√ √ √
|G| + 1
2 |G| +1 |G|
= (2 ) |G|
⎝ ⎠>2
≥ ≥2
|G|
√ √ √
log2 n +1 |G| |G|
= n |G| .
= (2 ) ≥ (2 )
log2 n


Damit ist (iv) begründet. Schließlich zeigen wir:
(v) Die Zahl n besitzt außer p keine weiteren Primteiler.
Angenommen, n besitzt einen weiteren Primteiler. Wir zeigen, dass dann |H| ¤

n |G| . Dazu betrachten wir die Menge
t
n
; 0 ¤ s, t ¤ |G|
s
J := .
p
p

t t
= ps , falls (s, t) = (s , t ), sodass
n n
Da n keine Potenz von p ist, gilt ps p p

2
|J | = |G| + 1 > |G| .
164 8 Primzahltests

Hiernach muss es verschiedene Zahlen m1 , m2 ∈ J , m1 = m2 , geben, die aber
modulo r kongruent sind, m1 ≡ m2 (mod r). Ohne Einschr¤nkung sei m1 > m2 ,
und m1 ’ m2 = r m mit einem m ∈ Z. Es gilt nun wegen

X m1 ’ X m2 = X m2 (X m1 ’m2 ’ 1) = X m2 (X r m ’ 1) = X m2 (X r ’ 1) g

für das Polynom g = X r(m’1) + X r(m’2) + · · · + X r + 1 ∈ Z[X] die Kongruenz

X m1 ≡ X m2 (mod (X r ’ 1)) .

Zu h ∈ H existiert ein Polynom f ∈ ∏k (X + a)ea ; ea ∈ N0 ⊆ Z p [X] mit
a=0
h = f (ξ). Es folgt wie beim Beweis der Gleichung (—)

f (X)m1 ≡ f (X m1 ) ≡ f (X m2 ) ≡ f (X)m2 (mod (X r ’ 1)) ,

also hm1 = hm2 . Daher ist h Nullstelle des Polynoms Q := Y m1 ’ Y m2 ∈ F p [Y].
Weil das für alle Elemente aus H gilt, und weil Q = 0 ist, folgt

√ √ √
|G|
n |G| |G|
¤ n |G| .
|H| ¤ deg(Q) = m1 ¤ ¤n
p
p

Das ist ein Widerspruch zu (iv). Damit ist (v) begründet.
Wegen (v) ist n eine Potenz von p. Und nun beachte man Schritt (1) im AKS-
Algorithmus, wonach n keine echte Potenz ist. Es folgt n = p.

Bemerkung
Unsere krude Analyse aus Lemma 8.10 und die Absch¤tzung r ¤ 5 führen auf
eine Laufzeitabsch¤tzung des beschriebenen AKS-Algorithmus von O( 18 ). Ge-
nauere Analysen und Modi¬kationen liefern wesentlich bessere Laufzeiten.


8.5 Vergleich der Primzahltests

Wir geben eine Übersicht über die behandelten Primzahltests:

Test Art Aufwand Bemerkung
deterministisch exponentiell nur für kleine Zahlen
Probedivision
probabilistisch polynomial kein echter Primzahltest
Fermat
probabilistisch polynomial das Mittel der Wahl
Miller-Rabin
deterministisch polynomial theoretische Bedeutung
AKS

Die Probedivison wird benutzt, um kleine Primteiler einer Zahl zu ¬nden. Der
Fermat-Test wird in der Praxis kaum benutzt, das Prinzip aber ist wesentlich für
die meisten bekannten Primzahltests. Der Miller-Rabin-Test ist das Mittel der Wahl
8.5 Vergleich der Primzahltests 165

für Primzahlen, wie sie etwa beim RSA-Verfahren benutzt werden, obwohl der
Test nur probabilistisch ist. Der Miller-Rabin-Test ist n¤mlich deutlich schneller
als der AKS-Test, und die Fehlerwahrscheinlichkeit von 4’k nach k Iterationen ist
nach hinreichend vielen Iterationen genügend klein. Der AKS-Test hat eine sehr
wichtige theoretische Bedeutung: Es gibt einen deterministischen Primzahltest
mit polynomialer Laufzeit. In der Sprache von Kapitel 4 heißt das: Das mathema-
tische Problem „prüfe, ob n eine Primzahl ist“ liegt in der Komplexit¤tsklasse P .



Aufgaben
8.1 Gibt es eine natürliche Zahl a = 1, sodass n = 15 starke Pseudoprimzahl
zur Basis a ist?
Welche natürlichen Zahlen zwischen 2 und 14 sind Zeugen für die Zusammen-
gesetztheit von n = 15?
8.2 Es sei n := 225593397919. Wie man beispielsweise mit Maple überprüfen
kann, ist
n = 2 207 · 6 619 · 15 443
die Primfaktorzerlegung von n.
(a) Schreiben Sie in einer Programmiersprache/-umgebung Ihrer Wahl ein Com-
puterprogramm, das den Fermat™schen Primzahltest für obiges n und a =
2, 3, . . . , 1 000 durchführt. Was f¤llt Ihnen bei den Ergebnissen der Tests auf?
(b) Versuchen Sie, die Ergebnisse aus (a) zu erkl¤ren.
Bestimmen Sie die kleinste Pseudoprimzahl zur Basis 2.
8.3
8.4 Begründen Sie: Sind p1 = 6 u1 + 1, p2 = 12 u2 + 1, p3 = 18 u3 + 1 mit
u1 , u2 , u3 ∈ N Primzahlen, so ist c = p1 p2 p3 eine Carmichael-Zahl.
8.5 Begründen Sie die in dem Beispiel auf Seite 153 gemachte Aussage, dass die
Ideale von Z genau die Mengen (k) = k Z, k ∈ N0 , sind.
8.6 Geben Sie einen polynomialen Algorithmus an, der prüft, ob eine natürliche
Zahl n der L¤nge = log2 (n) + 1 Potenz einer anderen natürlichen Zahl ist.
Gehen Sie wie folgt vor:
(a) Geben Sie ein möglichst kleines Intervall an, in dem alle möglichen Exponen-
ten liegen.
(b) Es sei e ein möglicher Exponent, d. h., n = de mit einem zu bestimmenden
’1
d ∈ N. Zeigen Sie zuerst 2 e ¤ d < 2 e und wenden Sie ein modi¬ziertes
Bisektionsverfahren an.
Zeigen Sie mit Induktion oder anders (2a+1) > 2a+1 für alle a ∈ N >1 .
8.7 a
9 Die Verfahren von Dif¬e und
Hellman, ElGamal und Rabin

Symmetrische Verschlüsselungsverfahren sind im Allgemeinen ef¬zienter als
Public-Key-Verfahren. Eine Möglichkeit, dies auszunutzen, aber dennoch das
Problem der Schlüsselverwaltung zu bew¤ltigen, haben wir bereits unter dem
Stichwort Hybridverfahren kennengelernt: Chiffriere eine Nachricht mit einem (ef-
¬zienten) symmetrischen Verfahren und den (kurzen) Schlüssel zum Dechiffrie-
ren dieser Nachricht mit einem Public-Key-Verfahren, und sende dann diese bei-
den Teile an den Empf¤nger (siehe Abschnitt 7.1.5).
Im vorliegenden Kapitel besprechen wir eine weitere trickreiche Variante, einen
Schlüssel über einen unsicheren Kanal auszutauschen, um dann die Kommuni-
kation mit einem symmetrischen Verfahren sichern zu können.
Beim Dif¬e-Hellman-Schlüsselaustausch wird ein geheimer Schlüssel über eine öf-
fentliche, nicht gesicherte Leitung ausgetauscht. Obwohl ein Angreifer den Aus-
tausch von Teilen des geheimen Schlüssels beobachten kann, ist er im Allgemei-
nen nicht in der Lage, aus diesen Teilen den Schlüssel selbst zu erzeugen. Die
Sicherheit des Verfahrens ist mit der Schwierigkeit des diskreten Logarithmen-
problems verbunden.
Das ElGamal-Verschlüsselungsverfahren ist ein Public-Key-Verfahren, das mit dem
Schlüsselaustausch von Dif¬e-Hellman zusammenh¤ngt. Daher ist auch die Si-
cherheit des ElGamal-Verfahrens an die Schwierigkeit des diskreten Logarith-
menproblems geknüpft. W¤hrend das Public-Key-Verfahren RSA in der Halb-
gruppe Z n realisiert ist, l¤sst sich das ElGamal-Verfahren in beliebigen endlichen
abelschen Gruppen implementieren. Das ElGamal-Verfahren auf einer elliptischen
Kurve “ das ist eine endliche abelsche Gruppe (siehe Kapitel 13) “ ist die derzeit
wohl bestuntersuchte Alternative zum RSA-Verfahren.
Als weiteres Public-Key-Verfahren stellen wir in diesem Kapitel das Rabin-Ver-
fahren vor. Der öffentliche Schlüssel n dieses Verfahrens ist ein Produkt zweier
Primzahlen. Das Rabin-Verfahren ¬ndet kaum praktische Anwendung, aber es
ist dafür von theoretischem Interesse: Es l¤sst sich zeigen, dass das Brechen des
Rabin-Verfahrens genauso schwierig ist wie das Faktorisieren von n. Beim RSA-
Verfahren ist dies nicht bekannt.


9.1 Der Dif¬e-Hellman-Schlüsselaustausch
Es sei p eine Primzahl. Wir beschreiben den Dif¬e-Hellman-Schlüsselaustausch in
der multiplikativen zyklischen Gruppe Z — der Ordnung p ’ 1 (siehe Satz 6.12).
p
168 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Jedes erzeugende Element der Gruppe Z — wird eine Primitivwurzel modulo p
p
— genau •(p ’ 1) Primitivwurzeln mo-
genannt. Nach Korollar 6.3 (b) besitzt Z p
dulo p, dabei bezeichnet • die Euler™sche •-Funktion.

Beispiel

Es ist 2 eine Primitivwurzel modulo 13, d. h. 2 = Z13 , da o(2) = 12:

k 1 2 3 4 5 6 7 8 9 10 11 12
k
2 2 4 8 3 6 12 11 9 5 10 7 1

Wegen Korollar 6.3 (a) sind die •(12) = 4 Primitivwurzeln modulo 13 die vier
1 5 7 11
Elemente 2 = 2, 2 = 6, 2 = 11, 2 = 7.


9.1.1 Der Schlüsselaustausch nach Dif¬e-Hellman
Beim Dif¬e-Hellman-Schlüsselaustausch wird ein (geheimer) Schlüssel über
einen öffentlichen, nicht gesicherten Kanal ausgetauscht, um dann mit einem
symmetrischen Verfahren zu kommunizieren. Eine abstrakte Version des Verfah-
rens wurde als Anwendung auf Seite 77 dargestellt.
ga

"
unsichere Leitung
Db H@
@@
˜˜ (p, g)
@@
˜˜ @@
˜˜
˜˜ gb
g ab g ab
Im hiesigen Kontext funktioniert das Verfahren so:

D und H einigen sich auf eine Primzahl p und eine Primitivwurzel g modulo
p : Es ist (p, g) öffentlich bekannt.

D w¤hlt ein a ∈ {2, . . . , p ’ 2}, bestimmt g a ∈ Z — und sendet A := g a an H
p
(der Exponent a bleibt geheim).

H w¤hlt ein b ∈ {2 , . . . , p ’ 2}, bestimmt gb ∈ Z — und sendet B := gb an D
p
(der Exponent b bleibt geheim).

D berechnet B a = g ab , H berechnet Ab = g ab .

Es haben dann D und H beide den geheimen Schlüssel g ab , obwohl g ab selbst
nicht über den unsicheren Kanal ausgetauscht wurde. Entscheidend ist die ein-
fache Tatsache, dass g ab = gba gilt. Vergleiche auch dazu die Anwendung auf
Seite 77. Der geheime Schlüssel kann nun etwa dazu dienen, um mit einem sym-
metrischen Verfahren zu kommunizieren.
9.1 Der Dif¬e-Hellman-Schlüsselaustausch 169

Beispiel
Es sei p = 17. Es ist 3 eine Primitivwurzel modulo 17.
7
7
D w¤hlt a = 7 ’ 3 = 11 =4
13
.
Austausch
4 4
H w¤hlt b = 4 ’ 3 = 13 =4
11

D und H haben beide den geheimen Schlüssel 4.

Bemerkung

Bei diesem Beispiel mit g = 3 ∈ Z17 kann ein Angreifer natürlich sofort g ab aus
g a und gb ermitteln. Es sind 7 = Logg (11) und 4 = Logg (13) leicht zu bestimmen,
folglich ist g28 = 4 der geheime Schlüssel. In der Praxis ist p so zu w¤hlen, dass
das diskrete Logarithmenproblem (vgl. Abschnitt 6.2.3) schwierig zu lösen ist.


9.1.2 Das Dif¬e-Hellman-Problem
Ein Angreifer, der den Schlüsselaustausch beobachtet, kennt die Größen

p , g , g a , gb , aber nicht a , b , g ab .

Das Dif¬e-Hellman-Problem lautet wie folgt:
Berechne g ab aus den Größen g, g a und gb .
Kann man das diskrete Logarithmenproblem lösen, so kann man auch das Dif¬e-
Hellman-Problem lösen. Man bestimme die diskreten Logarithmen a und b aus
den Gleichungen c = g a und d = gb und dann g ab mittels der dann bekann-
ten Größen g, a, b. Es ist bisher unbekannt, ob man das Dif¬e-Hellman-Problem
lösen kann, ohne diskrete Logarithmen berechnen zu können.

9.1.3 Der Mann in der Mitte
Wir beschreiben einen möglichen Angriff auf das eben geschilderte Verfahren von
Dif¬e und Hellman “ der Mann in der Mitte.
Die Teilnehmer D und H haben sich über einen unsicheren Kanal auf die Größen
p und g geeinigt. Ein Angreifer M kann also das Paar (p, g) beobachten. Noch
vor dem Austausch weiterer Größen zwischen D und H stellt sich M zwischen
die ahnungslosen D und H und geht dann wie folgt vor:

M f¤ngt g a von D ab und leitet ein g a mit einem nur ihm bekannten a an H
weiter (H denkt, g a kommt von D).

M f¤ngt gb von H ab und leitet ein gb mit einem nur ihm bekannten b an D
weiter (D denkt, gb kommt von H).

D bildet mit seinem a den vermeintlich geheimen Schlüssel gb a .
170 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

H bildet mit seinem b den vermeintlich geheimen Schlüssel g a b .

Weil M sowohl g a als auch gb als auch die Größen a , b kennt, kann M eben-
falls die Schlüssel gb a und g a b bilden.

M kann und muss jeden Geheimtext von D mit gb a entschlüsseln, und mit g a b
wieder verschlüsselt an H weiterreichen. Analog verf¤hrt er mit Nachrichten
von H an D.
Wenn dem Mann M in der Mitte ein Text entgeht, so ¬‚iegt er wahrscheinlich auf.
ga ga

 
M
DW HA
W AA
}}
} AA
}} AA
˜}} gb
gb
gb a ga b
Bemerkung
Varianten dieses Angriffs sind eine Bedrohung für jedes Verfahren der asymme-
trischen Kryptogra¬e. Schwachstelle ist die Übergabe des öffentlichen Schlüssels.
Wenn sich hier jemand dazwischen schalten kann, ist die gesamte Kommunika-
tion ungesichert. Für dieses Problem ist keine mathematische Lösung bekannt
(vielleicht auch gar nicht möglich). Es ist nur durch besondere Sorgfalt der Be-
nutzer einzud¤mmen.

9.1.4 Weitere Gruppen für das Dif¬e-Hellman-Verfahren
Das Dif¬e-Hellman-Verfahren kann offenbar in jeder endlichen zyklischen Grup-
pe G = g implementiert werden. Um Ef¬zienz und Sicherheit zu gew¤hrleisten,
sind solche Gruppen zu w¤hlen, in denen die Gruppenoperationen leicht durch-
führbar sind, das diskrete Logarithmenproblem (eigentlich das Dif¬e-Hellman-
Problem) aber schwer zu lösen ist. Günstige Gruppen sind die bereits benutzten
zyklischen Gruppen
Z — mit einer Primzahl p und
• p

• zyklische Untergruppen von elliptischen Kurven (diese werden wir in Ka-
pitel 13 behandeln).
Ungünstig sind die (additiven) zyklischen Gruppen
Z n mit n ∈ N.

In der additiven zyklischen Gruppe Z n ist das Berechnen diskreter Logarithmen
ef¬zient möglich. Wir begründen das. Man beachte zuerst, dass Potenzen wegen
der additiven Schreibweise zu Vielfachen werden. Nach Korollar 6.3 (a) gilt:

g = Z n ” ggT(g, n) = 1 .
9.2 Das ElGamal-Verschlüsselungsverfahren 171

Aus der Kenntnis von g und c = a · g kann leicht der diskrete Logarithmus a =
Logg c berechnet werden. Es ist hierzu nur die Kongruenzgleichung:

X g ≡ c (mod n)
zu lösen. Dies ist mit mithilfe des euklidischen Algorithmus aus Satz 4.10 ef¬zient
machbar: Man bestimme Zahlen x, y ∈ Z mit
1 = ggT(g, n) = x g + y n .
Es gilt dann c = (x c) g + y c n, also a g ≡ c (mod n) mit a := x c. Folglich ist nur
die ganze Zahl x zu bestimmen, um den diskreten Logarithmus a zu erhalten.
Wegen ggT(g, n) = 1 ist a + nZ nach Korollar 4.19 die Menge aller Lösungen.

Bemerkung
Man erkennt hier, dass es nicht die Struktur der Gruppe ist, die das DLP schwie-
rig macht “ alle zyklischen Gruppen derselben Ordnung sind isomorph. Es ist
vielmehr die Art der Beschreibung, die das bewirkt.

9.2 Das ElGamal-Verschlüsselungsverfahren
Das ElGamal-Verfahren ist verwandt mit dem Dif¬e-Hellman-Verfahren. Aber es
ist ein asymmetrisches Verschlüsselungsverfahren und kein Schlüsselaustausch.
Es gibt einen öffentlichen Schlüssel (p, g, A) und einen geheimen Schlüssel a.
Wir schildern die Funktionsweise.
C=(B, c)

!
G E
(p, g, A)


9.2.1 Schlüsselerzeugung
Gegeben seien eine Primzahl p, eine Primitivwurzel g modulo p und ein festes
a ∈ {2, . . . , p ’ 2}. Wir setzen A := g a . Beim ElGamal-Verschlüsselungsver-
fahren sind
(p, g, A) der öffentliche Schlüssel;

a (das a mit A = g a ) der geheime Schlüssel des Empf¤ngers E.


9.2.2 Verschlüsselung
Der Sender G sendet an E eine verschlüsselte Nachricht. Dazu besorgt sich G den
öffentlichen Schlüssel (p, g, A) von E. Es sei N ∈ Z — der Klartext.
p
G w¤hlt zuf¤llig eine Zahl b ∈ {2, . . . , p ’ 2}.
G berechnet B := gb ∈ Z — und c := Ab N ∈ Z — .
p p

G sendet den Geheimtext C = (B, c) an E.
172 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

9.2.3 Entschlüsselung
Erh¤lt der Empf¤nger E vom Sender G den Geheimtext C = (B, c), so berechnet
er mit seinem geheimen Schlüssel a das Element B’a c. Es gilt n¤mlich wegen
B = gb , c = Ab N und A = g a :

B’a c = g’a b Ab N = g’a b g a b N = N ,

und damit erh¤lt E den Klartext N ∈ Z — zurück.
p

Beispiel
Es sei p = 17. Das Element g = 3 ist eine Primitivwurzel modulo 17. Der Empf¤n-
ger E w¤hlt als geheimen Schlüssel a = 3 und hat somit den öffentlichen Schlüssel
(17, 3, 10).

Der Sender G verschlüsselt den Klartext 5 ∈ Z17 . Er w¤hlt b = 2 und erh¤lt den
Geheimtext (B, c) = (9, 7), den er an E sendet.
’3 —
Der Empf¤nger E erh¤lt nun wegen 9 = 8 in Z17 durch Berechnen von
’3
·7 = 8·7 = 5
9

den Klartext 5 zurück.

Man kann das ElGamal-Verfahren auf beliebige endliche zyklische Gruppen
G = g verallgemeinern. Wir werden das Verfahren in Kapitel 14 für zyklische
Untergruppen von elliptischen Kurven erneut schildern.

9.2.4 Zur Sicherheit des ElGamal-Verfahrens
Wir versetzen uns in die Situation eines Angreifers: Ein Angreifer, der den Aus-
tausch einer verschlüsselten Nachricht beobachtet, kennt die Größen

g , g a , gb , c = g a b N .

Kann der Angreifer A das Dif¬e-Hellman-Problem lösen, d. h., A kann aus g,
g a und gb das Element g a b bestimmen, so kann er auch das ElGamal-Verfahren
brechen. Er berechnet N = g’ab c. Kann andererseits A das ElGamal-Verfahren
brechen, d. h., A kann N aus der Gleichung c = g a b N bestimmen, so kann er
auch das Dif¬e-Hellman-Problem lösen. Er berechnet g a b = N ’1 c . Damit ist
gezeigt: Das Brechen des ElGamal-Verfahrens ist algorithmisch ¤quivalent zum
Lösen des Dif¬e-Hellman-Problems.
Das Dif¬e-Hellman-Problem kann gelöst werden, wenn man diskrete Logarith-
men berechnen kann. Um gegen die bekannten Algorithmen zum Berechnen
der diskreten Logarithmen gewappnet zu sein, sollte die Primzahl, die beim
ElGamal-Verfahren in Z — benutzt wird, etwa von der Größenordnung 1 024 Bit
p
sein. Wir werden in Kapitel 10 Algorithmen zum Berechnen diskreter Logarith-
men besprechen.
9.3 Das Rabin-Verschlüsselungsverfahren * 173

Bemerkung
Durch die Tatsache, dass die Primzahl p beim ElGamal-Verfahren in Z — etwa von
p
der Größenordnung von n beim RSA-Verfahren ist, ist das ElGamal-Verfahren in
Z — aufw¤ndiger als das RSA-Verfahren, da B = gb und c = Ab N zu berechnen
p
sind. Beim RSA-Verfahren ist hingegen nur N e zu berechnen. Implementiert man
aber das Verfahren von ElGamal auf einer elliptischen Kurve, wobei man etwa
die gleichen Sicherheitsanforderungen stellt, so ist ElGamal sogar ef¬zienter als
RSA, weil man mit deutlich kleineren Parametern auskommt.


9.2.5 Ein Angriff
Wird der Exponent b, den der Sender zum Chiffrieren seiner Nachricht N be-
nutzt, mehrfach zur Verschlüsselung von Nachrichten verwendet, so kann ein
Klartext durch einen Known-Plain-Text-Angriff ermittelt werden. Einem Angreifer
A ist ein zusammengehöriges Klartext-Geheimtext-Paar (N , C) bekannt. Folglich
kennt A auch das Element c = Ab N . Damit kann A aus einem weiteren Ge-
heimtext C = (B, c ), der mit demselben b erzeugt wurde, den dazugehörigen
Klartext N aus c = Ab N ermitteln; er berechnet dazu:

c’1 N c = A’b N ’1 N Ab N = N .

Folglich kann N aus c, c und N ermittelt werden. Es ist also bei jedem Durch-
gang ein neues b aus der Menge {2, . . . , p ’ 2} zu w¤hlen. Das hat einen wei-
teren Vorteil: Man kann zweimal denselben Klartext verschicken, ohne dass ein
Angreifer das merkt. Die Geheimtexte sind verschieden.

9.3 Das Rabin-Verschlüsselungsverfahren *
Das Problem, eine natürliche Zahl in ein Produkt von Primzahlen zu faktorisie-
ren, wird als außerordentlich schwierig angesehen. Ist n ein Produkt von zwei
Primzahlen p und q der Größenordnung 512 Bit, wie sie beim RSA-Verfahren
verwendet werden, so braucht ein moderner Rechner unvertretbar lange Zeit, um
die Primzahlen p und q zu ermitteln. Wir werden moderne und ef¬ziente Faktori-
sierungsalgorithmen in Kapitel 11 vorstellen. Es ist aber offen, ob nicht bereits in
n¤chster Zukunft ein Verfahren entdeckt wird, mittels dessen die Faktorisierung
deutlich ef¬zienter möglich ist.
Das Verfahren von Rabin ist ein Public-Key-Verfahren mit einem öffentlichen
Schlüssel n, der ein Produkt zweier Primzahlen ist. Das Verfahren zu brechen
ist algorithmisch ¤quivalent zur Faktorisierung der Zahl n.


9.3.1 Quadratwurzeln modulo n

Es sei n ∈ N. Ein Element b ∈ Z — heißt eine Quadratwurzel modulo n von
n
2
a ∈ Z — , falls b = a; das Element a nennt man dann ein Quadrat modulo n.
n
174 9 Die Verfahren von Dif¬e und Hellman, ElGamal und Rabin

Beispiel

In Z15 = {1, 2, 4, 7, 8, 11, 13, 14} sind die Elemente 1 und 4 die Quadrate. Das
Element 1 hat die Quadratwurzeln 1, 4, 11, 14 und das Element 4 die Quadrat-
wurzeln 2, 7, 8, 13.

Es ist kein Zufall, dass jedes Quadrat in Z15 genau vier Wurzeln hat.

Lemma 9.1
Es sei n = p1 · · · pt mit verschiedenen ungeraden Primzahlen p1 , . . . , pt . Ein Element
a ∈ Z — besitzt keine oder genau 2t Quadratwurzeln.
n

Beweis. Wegen Lemma 7.5 können wir Z — mit Z —1 — · · · — Z —t identi¬zieren. Ist
n p p
— — · · · — Z — eine Quadratwurzel von a = (a , . . . , a ), so
b = (b1 , . . . , bt ) ∈ Z p1 t
1
pt
ist offenbar jedes Element von W := {(±b1 , . . . , ±bt )} eine Quadratwurzel von
a. Ist nun c = (c1 , . . . , ct ) ∈ Z —1 — · · · — Z —t eine weitere Quadratwurzel von
p p
a = (a1 , . . . , at ), so ist ci eine Nullstelle des Polynoms X 2 ’ ai über dem Körper
Z pi für alle i = 1, . . . , t. Somit ist ci = ±bi für alle i = 1, . . . , t (siehe Satz 3.9), d. h.
c ∈ W. Damit ist W die Menge aller Quadratwurzeln, und es gilt |W| = 2t .

Bemerkung
Wie der Beweis zeigt, erh¤lt man die Quadratwurzeln b modulo n von a folgen-
dermaßen aus den Quadratwurzeln von ai modulo pi für i = 1, . . . , t:
Gegeben ist ein Element (b1 , . . . , bt ) ∈ W. Es gilt folglich bi ≡ ai (mod pi ) für
2

i = 1, . . . , t. Bestimme mit dem chinesischen Restsatz 7.4 ein Element b ∈ Z mit
b ≡ bi (mod pi ) für i = 1, . . . , t .
Es ist dann b eine Quadratwurzel von a modulo n.

Wir halten für sp¤tere Zwecke eine einfache Folgerung fest.

Korollar 9.2
Es sei n = p1 · · · pt mit verschiedenen ungeraden Primzahlen p1 , . . . , pt . Dann existie-
•(n)
ren genau 2t Quadrate in Z — . n

Beweis. Wir betrachten die Abbildung
Z— ’ Z—
n n
q: .
’a 2
a

Jedes Quadrat b ∈ Z — hat nach Lemma 9.1 genau 2t Quadratwurzeln, d. h.
n
|q’1 (b)| = 2t . Da Z — die disjunkte Vereinigung von Mengen der Form q’1 (b)
n
mit einem Quadrat b in Z — ist, erhalten wir für die Anzahl der Quadrate in Z — :
n n

|Z — | •(n)
|q(Z — )| = = t.
n
n
|q’1 (b)| 2
Das ist die Behauptung.
9.3 Das Rabin-Verschlüsselungsverfahren * 175

9.3.2 Quadratwurzeln modulo p ≡ 3 (mod 4)
2
Es sei p eine Primzahl kongruent 3 modulo 4. Ist a ein Quadrat in Z — , a = b
p

<<

. 6
( 9)



>>