Cryptography Reference
In-Depth Information
8.1 Probedivision
Wir betrachten eine ungerade natürliche Zahl
n
.
8.1.1 Das Verfahren
Jeder praktische Primzahltest und auch jeder Faktorisierungsalgorithmus be-
ginnt mit
Probedivisionen
. Man prüft hierbei, ob die Zahl
n
durch
kleine
, be-
kannte Primzahlen 3, 5, 7, 11, 13 . . . teilbar ist. Das macht man effizient mit der
Division mit Rest. Bleibt bei Division von
n
durch
p
kein Rest, so hat man einen
Teiler von
n
gefunden, d. h.,
n
ist keine Primzahl.
Die kleinen Primzahlen führt man in einer Liste. Typischerweise ist diese Liste so
gestaltet, dass man alle Elemente in 16-Bit-Wörtern speichern kann. Ein andere
Weg ist es, das Produkt dieser Primzahlen zu speichern und den ggT mit
n
zu
bestimmen. Nur wenn dieser Test negativ ausfällt, es also keine
kleinen
Primteiler
gibt, fährt man mit einem spezielleren Verfahren fort. Heute ist das meist der
Miller-Rabin-Test
.
Beispiel
Wir teilen die Zahl
n
=
253 mit Rest nacheinander durch die Primzahlen 2, 3, 5, 7
und 11 und finden die Zerlegung
n
=
11
·
23 .
8.1.2 Probedivision für große Zahlen
Prinzipiell ist es möglich, die Zahl
n
auf Primalität durch Probedi
v
isionen zu
überprüfen. Dazu muss man aber alle Primzahlen kleiner gleich
√
n
durchpro-
bieren. Ist nämlich
n
keine Primzahl, dann gilt für den kleinsten echten Teiler
p
von
n
≤
√
n
.
Ist aber
n
eine große Zahl, so ist die Menge aller Primzahlen kleiner gleich
√
n
sehr umfangreich, die Probedivision also sehr aufwändig. Wir schildern dies et-
was genauer und bezeichnen dazu mit
p
π
die
Primzahlfunktion
:
π
(
x
)=
| {
p
∈
P
;
p
≤
x
} |
,
x
∈
R
>
0
.
Der
Primzahlsatz
- von A. Legendre und C. F. Gauß vermutet, aber erst um 1896
von J. S. Hadamard und C. de La Vallée Poussin bewiesen - besagt:
Der Primzahlsatz.
Für x
∈
R
>
0
gilt:
x
log
x
,
log
x
x
π
(
x
)
∼
d. h.
lim
x
→
∞
π
(
x
)
·
=
1.
