Cryptography Reference
In-Depth Information
8 Primzahltests
Große Primzahlen sind für viele Verschlüsselungsverfahren von fundamentaler
Bedeutung. Es existieren auch beliebig große Primzahlen, da die Menge
aller
Primzahlen unendlich ist. Aber es ist bisher keine
Konstruktionsmethode
für Prim-
zahlen bekannt, also etwa eine effizient berechenbare Funktion
f
P
N
→
P
:
mit
unendlicher Bildmenge.
Um eine große Primzahl zu finden, wählt man in der Praxis eine ungerade natür-
liche Zahl
n
der gewünschten Größenordnung und prüft diese Zahl
n
auf Prima-
lität, d. h., man prüft, ob
n
eine Primzahl ist. Dazu benutzt man sogenannte
Prim-
zahltests
. Stellt sich bei einem solchen Test heraus, dass die Zahl
n
keine Primzahl
ist, so überprüft man eine zu
n
nächstgelegene ungerade natürliche Zahl. Dabei
garantiert der
Primzahlsatz
, dass in der
Nähe
von
n
mit hoher Wahrscheinlichkeit
eine Primzahl liegt.
Wir stellen in diesemKapitel vier Primzahltests vor, die
Probedivision
, den
Fermat-
Test
, den
Miller-Rabin-Test
und den
AKS-Test
. Die Tests unterscheiden sich in ih-
rer Komplexität und ihrer Genauigkeit: Zwei der Tests - die Probedivision und
der AKS-Test - beweisen das Vorliegen einer Primzahl. Die anderen beiden Tests
liefern bei positivem Ausgang des Tests nur Vermutungen darüber, ob eine Prim-
zahl vorliegt. Tatsächlich liefern sie bei negativem Ausgang des Tests einen Be-
weis, dass
n
keine Primzahl ist, und sind also streng genommen Tests auf Zusam-
mengesetztheit.
Der Miller-Rabin-Test ist heutzutage für das Auffinden großer Primzahlen, wie
man sie etwa für das RSA-Verfahren benutzt, das Mittel der Wahl. Er ist ein
pro-
babilistischer
Test, d. h., liefert der Test die Aussage „
n
“, so ist
n
tatsächlich
nur mit einer gewissen Wahrscheinlichkeit eine Primzahl. Die Aussage „
n
∈
P
∈
P
“
kann beim Miller-Rabin-Test mit einer gewissen, kontrollierbar kleinen Fehler-
wahrscheinlichkeit falsch sein.
Im Gegensatz dazu heißt ein Test
deterministisch
, wenn er stets ein korrektes
Ergebnis liefert, d. h., wenn der Test das Ergebnis „
n
∈
P
“ ausgibt, so ist
n
auch
ganz bestimmt eine Primzahl.
Wir bezeichnen die Menge aller Primzahlen stets mit
P
. Eine natürliche Zahl
n
∈
N
>
1
mit
n
=
nennen wir
zusammengesetzt
, wenn es Zahlen
a
,
b
ab
gibt. Die
zusammengesetzten Zahlen sind damit die natürlichen Zahlen ungleich 1, die
keine Primzahlen sind.
