Cryptography Reference
In-Depth Information
Der Beweis des Primzahlsatzes ist Thema der analytischen Zahlentheorie (man
vgl. etwa [5]).
Beim RSA-Verfahren benutzt man üblicherweise Primzahlen, die größer als 2
512
sind. Nach dem Primzahlsatz existieren also etwa
2
512/2
log 2
512/2
10
74
>
Primzahlen kleiner oder gleich
√
2
512
. Daran erkennt man, dass Probedivision
allein als Primzahltest für unsere Zwecke völlig unzureichend ist.
Der Primzahlsatz zeigt aber auch, dass die zufällige Wahl einer ungeraden Zahl
und ein Test auf Primalität eine Erfolg versprechende Strategie ist um Primzahlen
zu finden. Es gilt nämlich für die gewählte Zahl
n
∈
N
:
π
(
)
n
1
log
n
,
≈
n
1
d.h., die
Dichte
der Primzahlen um die Zahl
n
herum ist ungefähr
log
n
, sodass in
einem Intervall der Länge log
n
um
n
ungefähr eine Primzahl liegt. Gilt
n
2
512
,
≈
≈
so sind also etwa log
n
355 Zahlen zu überprüfen - eine relativ kleine Anzahl.
8.1.3 Sichere und Mersenne'sche Primzahlen
∈
P
Um sichere Primzahlen
p
zu finden (vgl. Seite 104), modifiziert man die in
der Einleitung beschriebene Strategie wie folgt: Man ermittelt zuerst eine Prim-
zahl
q
und testet dann, ob
p
:
=
+
1 eine (dann sichere) Primzahl ist. Im All-
gemeinen ist es sehr
schwierig
, sichere Primzahlen zu bestimmen. Über sichere
Primzahlen ist nur wenig bekannt, man weiß nicht einmal, ob es unendlich viele
solche Primzahlen gibt.
Die größten bekannten Primzahlen sind die sogenannten
Mersenne'schen Prim-
zahlen.
Das sind Primzahlen der Form 2
n
2
q
. Damit die Zahl 2
n
−
∈
N
−
1
eine Primzahl sein kann, muss auch der Exponent
n
eine Primzahl sein; andern-
falls wäre für
n
1 mit
n
∈
N
>
1
die Zahl 2
a
1 ein echter Teiler von 2
n
=
−
−
ab
mit
a
,
b
1,
da gilt:
2
n
2
ab
2
a
b
2
a
2
a
b
−
1
2
a
−
1
=
−
1
=(
)
−
1
=(
−
1
)((
)
+
···
+
+
1
)
.
Man kennt bisher 47 Mersenne'sche Primzahlen, die größte ist
2
43.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 2
n
−
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.
