selten Daten zu gewinnen. Der Begriff Krytopgrafie wird aber häufig für Kryptologie
verwendet.
Viele der Verfahren, die zur Verschlüsselung in der Kryptologie genutzt werden, beruhen
auf dem Nutzen von möglichst großen Primzahlen. Hier haben Zahlen, die prim sind und
vorzugsweise mehr als 100 Stellen haben, eine fundamentale Bedeutung.
Eines der bekanntesten Verfahren, welches die Verschlüsselung mittels großer Primzahlen
nutzt, möchte ich kurz vorstellen, um einen Alltagsbezug des Themas herzustellen.
1.2.1 RSA-Verfahren
Das Verfahren wurde 1977 von R. L. R
IVEST
, A. S
HAMIR
und L. A
DLEMAN
vorgestellt
und zählt zur Klasse der Public-Key-Verfahren, das heißt, der Schlüssel zum Verschlüs-
seln ist öffentlich zugänglich und funktioniert folgendermaßen:
Möchte der Sender S an den Empfänger E eine Nachricht N senden, so benutzt S einen
öffentlichen Schlüssel e von E, den er in einem öffentlichen Verzeichnis findet. Dieser
Schlüssel e wird auf N angewendet, und an E wird der erhaltende Code C = e(N )
gesendet. Der Empfänger E hat wiederum einen geheimen Schlüssel d, mit dessen Hilfe
er aus dem Geheimtext C die Nachricht N wieder herstellen kann, denn N = d(e(N )).
Die Sicherheit dieses Verfahrens beruht auf der Tatsache, dass aus dem Code C = e(N )
und dem öffentlichen Schlüssel e, keine Rückschlüsse in angemessener Zeit auf die Nach-
richt N und den geheimen Schlüssel d zu ziehen sind.
Damit die Sicherheit gewährleistet wird, ist es für das Verfahren sehr wichtig, dass es
im Allgemeinen sehr schwer ist, eine (beim Verfahren benutzte und öffentlich bekannte)
große natürliche Zahl n in ihre Primfaktoren zu zerlegen.
Das hierfür verwendete Kryptosystem ist asymmetrisch und zählt zu der Klasse der Ex-
ponentiationschiffren. Die Nachricht N , aufgefasst als Element von
Z
n
, n
N, wird über
den Sender S verschlüsselt, indem mit dem öffentlichen Schlüssel e von E eine Potenz
von N gebildet wird:
S
C
=N
e
Z
n
-
(n,e)
E
Der Empfänger E hat den geheimen Schlüssel d so bestimmt, dass C
d
= (N
e
)
d
= N
ergibt. Zu beachten ist außerdem, dass beide Schlüssel (also sowohl d als auch e) vom
Empfänger E stammen. Das heißt, der öffentliche Schlüssel e ist jedem zugänglich, ergo
kann jeder eine Nachricht an E schicken. Aber nur der Empfänger E kennt den geheimen
Schlüssel d zum Entschlüsseln der Nachricht N . Folgerichtig kann nur E und niemand
anderes (nicht einmal der Sender S) seine Nachricht N entschlüsseln.
4
Für n
N mit (n) als E
ULERSCHE
F
UNKTION
gilt:
(n) =
| Z
×
n
|=|{a N; 1 a n, ggT (a, n) = 1} |,
wobei für zwei verschiedenen Primzahlen p und q, n = pq ist.
Die Klartextmenge P und die Geheimtextmenge C sind beides gleich
Z
n
, die Schlüssel-
menge ist mit
K =
{e N; ggT (e, (n)) = 1}
gegeben.
Die Verschlüsselungsfunktion f
e
mit e
K ist definiert durch f
e
(N ) = N
e
für N
P .
Letztendlich ist die Entschlüsselungsfunktion f
d
mit d
K definiert über f
d
(C) = C
d
für C
C, wobei gilt, dass ed 1(mod(n)). Dabei wird d mit Hilfe des euklidischen
Algorithmus zu e
K bestimmt. Die Entschlüsselung einer verschlüsselten Nachricht N
liefert also wieder die Nachricht N selbst:
f
d
(f
e
(N )) = f
d
(N
e
) = N
ed
= N
Zu beachten ist hierbei, dass die Zahlen n = pq und e öffentlich bekannt sind. Dem
potenziellen Angreifer darf die Zahl (n) = (p
-1)(q-1) nicht bekannt sein. Er kann nun,
ebenso wie der Empfänger E, unter Nutzung des euklidischen Algorithmus den geheimen
Schlüssel d ermitteln. Wählt man die Primzalen p und q allerdings entsprechend groß, ist
es im Allgemeinen sehr schwierig, aus der Kenntnis n = pq die Primfaktoren p und q
und damit (n) = (p
- 1)(q - 1) zu ermitteln. In der Praxis werden Primzahlen der
Größenordnung 512 Bit gewählt. (vgl. [KK10], Kapitel 7)
Um nun solch einen sicheren Schlüssel d zu erzeugen, werden ausreichend große Prim-
zahlen benötigt. Und genau das ist der zentrale Anknüpfungspunkt zu den Primzahltests.
Bisher existiert keine Möglichkeit, Primzahlen zu konstruieren, "also etwa eine effizient
berechenbare Funktion f :
N P mit unendlicher Bildmenge." ([KK10], S.141). Daher
wird in der Praxis folgendes Vorgehen angewendet: Man wählt eine beliebig große, un-
gerade natürliche Zahl n und prüft diese, ob sie eine Primzahl ist. Ergibt ein solcher Test,
dass dies nicht der Fall ist, überprüft man eine ungerade natürliche Zahl in der Nähe von
n. Denn der Primzahlsatz besagt, dass mit einer großen Wahrscheinlichkeit eine Primzahl
in der Nähe von n liegt.
5
2 Primzahltests
Solche Tests zum Überprüfen, ob eine Zahl prim ist, werden als Primzahltests bezeichnet.
Dabei unterscheiden sich die verschiedenen Tests sowohl in ihrer Komplexität, als auch in
ihrer Genauigkeit. So unterscheidet man zwischen probabilistischen oder randomisierten
Tests, welche aussagen, dass n nur mit einer gewissen Wahrscheinlichkeit wirklich eine
Primzahl ist, und deterministischen Tests, das heißt, es wird stets ein konkretes Ergebnis
geliefert. Wenn der Test also ergibt, dass n eine Primzahl ist, dann ist dies bei determinis-
tischen Tests tatsächlich so, während die probabilistischen nur eine Vermutung aufstellen,
dass es mit großer Wahrscheinlichkeit so ist.
Im Folgenden werde ich verschiedene Primzahltests vorstellen und ein Fazit zu ihrer An-
wendungstauglichkeit ziehen. Der erste Test, mit dem ich mich beschäftigen möchte, ist
nicht nur ein Primzahltest, sondern auch Voraussetzung für andere speziellere Verfahren.
2.1 Probedivision
Bei der Probedivision überprüft man, ob die Zahl n durch eine kleine, bekannte Primzahl
p teilbar ist. Effizient wird eine Division mit Rest durchgeführt. Bleibt bei der Division
durch p kein Rest, so hat man einen Teiler gefunden, das heißt, n ist keine Primzahl. Die
Methode beruht auf dem einfachen Satz 1:
Wenn n eine zusammengesetzte natürliche Zahl ist, dann hat n Primteiler p,
der nicht größer ist als
n.
Den Beweis kann man kurz fassen, indem man n als das Produkt zweier
natürlicher Zahlen x und y schreibt, für die jeweils gilt 1 < x, y
n.
Da jede natürliche Zahl m > 1 einen Primteiler hat, haben auch x und y
Primteiler. Diese müssen auch n teilen, somit folgt die Behauptung.
(vgl.
Buchmann 2010 [Buc10], S.125).
Ein Beispiel wäre die Zahl n = 403; diese wird nacheinander mit Rest durch die be-
kannten kleinen Primzahlen 2, 3, 5,7, 11 und 13 dividiert. Schlussendlich ergibt sich die
n = 13
· 31.
Die Überprüfung von großen Zahlen auf Primalität ist prinzipiell möglich. Da man aber
alle Primzahlen kleiner gleich
n zur Division durchprobieren muss, ist diese Methode
vor allem bei sehr großen Zahlen, wie sie in der Kryptologie bevorzugt werden, ineffizi-
ent, da die Bestimmung mit einem großen Aufwand verbunden ist. Die Primzahlen, die
für die Division möglich sind, erstellt man typischerweise in einer Liste, meistens mit
Hilfe des S
IEB DES
E
RATOSTHENES
.
6
2.2 Siebmethoden
Das S
IEB DES
E
RATOSTHENES
gehört zur Klasse der Siebmethoden, welche ein Teilge-
biet der analytischen Zahlentheorie sind, welche wiederum der Zahlentheorie angehört.
Siebmethoden beschäftigen sich mit den Eigenschaften der ganzen Zahlen, welche mit
Addition und vor allem Multiplikation zusammenhängen, also Teilbarkeit, Faktorzerle-
gung, Restklassen und auch Primzahlen, was in diesem Kontext besonders interessant ist.
Inhaltlich befassen sie sich hauptsächlich sowohl mit der Bestimmung der Anzahl aller
Zahlen unterhalb einer gegebenen Schranke, wobei die Zahlen alle eine bestimmte Eigen-
schaft haben, als auch mit der Abschätzung von Summen zahlentheoretischer Funktionen.
2.2.1 Sieb des Eratosthenes
Das S
IEB DES
E
RATOSTHENES
ist wohl einer der einfachsten Primzahltests und wohl
der älteste bekannte Test, um alle Primzahlen zu ermitteln, die kleiner oder gleich einer
vorgegeben Zahl sind. Benannt wurde der Algorithmus nach dem griechischen Mathe-
matiker E
RATOSTHENES VON
K
YRENE
, der im 3. Jahrhundert v. Chr. lebte. Allerdings
führte dieser nur die Bezeichnung "Sieb" für das Verfahren ein, welches schon lange vor
seiner Zeit bekannt war. E
RATOSTHENES
ist ebenfalls für seine recht genaue Berechnung
des Erdumfangs bekannt, um die es hier aber in keiner Weise gehen soll.
Die Idee ist, nach und nach alle zusammengesetzten Zahlen bis zu einer bestimmten vor-
gegebenen Zahl "auszusieben", so dass am Ende nur noch die Primzahlen übrig bleiben.
Zur Beschreibung der Vorgehensweise halte ich mich an (Rempe 2009 [RW09], Abschnitt
1.5).
Zuerst werden alle Zahlen von 1 bis zu einer frei gewählten natürlichen Zahl N , welche
die obere Schranke darstellt, aufgeschrieben. Danach wird wie folgt verfahren:
· Da 1 keine Primzahl ist, wird sie gestrichen und bei 2 begonnen.
· 2 muss eine Primzahl sein, da als Teiler höchstens 1 und 2 in Frage kommen. Die
Vielfachen von 2, angefangen von 4, werden nun gestrichen, da sie nicht prim sein
können.
· Die nächste Zahl welche stehen geblieben ist, ist die 3, diese muss also eine Prim-
zahl sein. Analog zu Schritt 2, werden nun alle Vielfachen von 3, beginnend bei 6,
gestrichen.
· Die nächste nicht durchgestrichenen Zahl ist 5, und wiederrum werden hier alle
Vielfachen der Zahl gestrichen. Dieses Vorgehen wird fortgesetzt bis zu
N . Alle
Zahlen zwischen
N und N, die keine Primzahlen sind, müssen mindestens einen
Faktor besitzen, der höchstens so groß wie
N ist, und wurden somit bereits ge-
strichen. Siehe dazu auch den Satz und Beweis unter 2.1. Alle nichtgestrichenen
Zahlen zwischen 1 und N sind also die Primzahlen.
7
Das ganze soll an einem Beispiel verdeutlicht werden. Für N = 400 sieht das Sieb am
Ende wie folgt aus, dabei stehen die unterschiedlichen Graustufen für die einzelnen Sieb-
schritte:
Abbildung 1: Sieb des Eratosthenes für N = 400
Die resultierenden Primzahlen zwischen 1 und 400 sind demnach folgende
78:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101
103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191
193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283
293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
Diese Methode ist leicht einsehbar für jedermann, deswegen möchte ich im Kapitel 3
noch einmal auf diesen Algorithmus zurückkommen. Des Weiteren lässt sich das Ver-
fahren sehr einfach auf den Computer implementieren und verwenden. Jedoch ist der
Algorithmus für die Praxis, mit hunderten oder mehr Stellen, nicht zu gebrauchen, da
die Berechnung und Streichung der einzelnen Zahlen zu viel Zeit in Anspruch nimmt.
Deswegen ist dieses Verfahren ineffizient.
2.2.2 Sieb von Atkin
Eine Optimierung des S
IEB DES
E
RATOSTHENES
ist das S
IEB VON
A
TKIN
, welches
schneller arbeitet, ebenfalls aber alle Primzahlen bis zu einer gewissen oberen Grenze
bestimmt. Der Algorithmus wurde von A. O. L. A
TKIN
und D
ANIEL
J. B
ERNSTEIN
entwickelt und ist wie folgt aufgebaut. Dabei orientiere ich mich an den Darstellungen
von A
TKIN
& B
ERNSTEIN
1999 ([AB99]) und 2004 ([AB04]).
8
· Die erste Festlegung sagt aus, dass alle Reste Modulo 60 Reste sind.
· Alle Zahlen, auch die Variablen x und y, sind natürliche Zahlen.
· In folgender Darstellung bedeutet Invertieren, dass das Merkmal (prim oder nicht-
prim) eines Eintrages in der Siebliste zum Gegenteil gewechselt wird.
1. Es wird eine Ergebnisliste erstellt, die mit 2, 3 und 5 gefüllt ist.
2. Es wird eine Siebliste mit allen natürlichen Zahlen erstellt, die am Anfang alle
auf das Merkmal "nicht-prim" gesetzt werden.
3. Für jeden Eintrag in der Siebliste wird Folgendes ausgeführt:
Falls der Eintrag eine Zahl mit Rest 1, 13, 17, 29, 37, 41, 49, oder 53
enthält, invertiere ihn für jede mögliche Lösung der Gleichung:
4x
2
+ y
2
= Eintragszahl.
Falls der Eintrag eine Zahl mit Rest 7, 19, 31, oder 43 enthält, invertiere
ihn für jede mögliche Lösung der Gleichung:
3x
2
+ y
2
= Eintragszahl.
Falls der Eintrag eine Zahl mit Rest 11, 23, 47, oder 59 enthält, invertiere
ihn für jede mögliche Lösung der Gleichung:
3x
2
-y
2
= Eintragszahl, wobei x > y.
4. Begonnen wird bei der kleinsten Zahl.
5. Die nächste Zahl, die in der Siebliste als prim markiert ist, wird der Ergebnis-
liste zugeführt.
6. Diese Zahl wird quadriert und alle Vielfachen des Quadrates in der Siebliste
als nicht-prim gekennzeichnet.
7. Wiederhole Schritt 5-7.
Der im ersten Moment etwas verwirrend aussehende Algorithmus lässt sich schnell und
einleuchtend erklären.
Es werden alle Zahlen ignoriert, die durch 2, 3 oder 5 teilbar sind, denn:
· Alle natürlichen Zahlen, die mit Modulo 60 Rest 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,
22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56, oder 58 ergeben,
lassen sich durch 2 teilen und sind somit keine Primzahlen.
9
· Alle Zahlen mit Modulo 60 Rest 3, 9, 15, 21, 27, 33, 39, 45, 51, oder 57 sind
wiederum teilbar durch 3 und daher nicht prim.
· Analog sind alle natürlichen Zahlen mit Modulo 60 Rest 5, 25, 35, oder 55 durch 5
teilbar und somit nicht prim. Diese Reste werden alle ignoriert.
· Des Weiteren haben alle Zahlen mit Modulo 60 Rest 1, 13, 17, 29, 37, 41, 49, oder
53 einen Modulo 4 Rest von 1. Diese Zahlen sind genau dann Primzahlen, wenn
die Anzahl an Lösungen für 4x
2
+ y
2
= n ungerade ist und die Zahl quadratfrei ist.
· Alle natürlichen Zahlen mit Modulo 60 Rest 7, 19, 31, oder 43 haben einen Modulo
6 Rest von 1. Jene Zahlen sind genau dann prim, wenn die Anzahl der Lösungen
für 3x
2
+ y
2
= n ungerade ist und die Zahl wieder quadratfrei ist.
· Entsprechend weisen alle Zahlen mit Modulo 60 Rest 11, 23, 47, oder 59 einen
Modulo 12 Rest von 11 auf. Diese Zahlen sind genau dann prim, wenn die Anzahl
an Lösungen für 3x
2
-y
2
= n ungerade ist. Auch hier wird die Quadratfreiheit
vorausgesetzt.
Neben diesen sich recht ähnlichen Siebmethoden, gibt es auch noch andere, so zum Bei-
spiel die Folgenden, welche ich nur kurz erwähnen möchte.
2.2.3 Weitere Siebmethoden
In meinen Recherchen fand ich heraus, dass die B
RUN
sche Siebmethode vor allem bei
der Untersuchung von Primzahlzwillingen, also Primzahlen, die nur durch eine zusam-
mengesetzte Zahl voneinander getrennt werden, Anwendung finden. Primzwillinge sind
zum Beispiel (11; 13) oder (17; 19), aber auch (387; 389). Bis heute ist ungeklärt, ob die
Menge der Primzwillinge ebenso unendlich ist wie die Menge der Primzahlen selbst.
Mit der B
RUN
schen Siebmethode, welche 1920 von dem norwegischen Mathematiker
V
IGGO
B
RUN
in die Zahlentheorie eingeführt wurde, sind untere und obere Abschätzun-
gen möglich, die nahezu auf dem gleichen Weg gewonnen werden können. Im Einzelnen
sind sie jedoch recht mühsam.
Eine deutlich einfachere Abschätzung, zumindest nach oben, erhält man durch die S
EL
-
BERG
sche Siebmethode. Aber auch hier beschäftigt sich die Siebmethode mit der Be-
stimmung von Primzahlzwillingen. A
TLE
S
ELBERG
war ein Schüler von B
RUN
und ver-
öffentlichte 1947 seine verbesserte Variante des B
RUN
schen Siebes.
10
2.3 Probabilistische Primzahltests
2.3.1 Fermat-Test
Der Primzahltest von F
ERMAT
beruht auf dem kleinen Satz von F
ERMAT
, den ich unter
2.4 noch näher beleuchten möchte. Er dient dazu, zusammengesetzte Zahlen von Prim-
zahlen zu unterscheiden.
Wenn n
2 eine beliebige natürliche Zahl ist, kann mit einer beliebigen zu n teiler-
fremden natürlichen Zahl a mit 1
a < n , einer sogenannten Basis, überprüft werden,
ob a
n
-1
1 (mod n) gilt. Ist die Kongruenz nicht erfüllt, gilt wegen des kleinen Satzes
von F
ERMAT
, dass n zusammengesetzt ist. Darauf basiert der folgende Algorithmus, der
F
ERMAT
-Test.
· Eingabe: n
zu testende Zahl; Ergebnis: zusammengesetzt oder keine Aussage
· Wähle (z.B. per Zufall) eine beliebige natürliche Zahl a mit 1
a < n.
· Falls ggT (a, n) = 1 ist, ist das Ergebnis zusammengesetzt.
· Ansonsten: Wenn a
n
-1
= 1 (mod n) dann ist das Ergebnis zusammengesetzt, sonst
ist das Ergebnis keine Aussage.
Wird der Test mehrfach unter Anwendung verschiedener Basen durchgeführt und tritt
immer wieder das Ergebnis "keine Aussage" auf, so kann dieses so interpretiert werden,
dass n vermutlich eine Primzahl ist.
Durch den Test können Primzahlen sicher als solche erkannt werden, das garantiert der
kleine
FERMAT
sche Satz. Ein Problem ist allerdings, dass der Test einige zusammenge-
setzte Zahlen nicht als solche erkennt. Diese Zahlen nennt man Pseudoprimzahlen zu
einer bestimmten Basis a. "Zum Beispiel ist jede ungerade zusammengesetzte Zahl n ei-
ne Pseudoprimzahl zur Basis a = n
- 1. Es gibt aber auch andere Beispiele. Etwa ist
11
14
= (11
2
)
7
= 121
7
1
7
= 1 (mod 15), obwohl 15 nicht prim ist. Wenn wir also 15
eingeben und zufällig die Basis 11 gewählt wird, dann erkennt der F
ERMAT
-Test 15 nicht
als zusammengesetzt." ([RW09], S. 84)
Da der Test probabilistisch ist, sollte er öfter durchgeführt werden, um die Chance von
Fehlerkennungen zu minimieren. Die spannende Frage lautet: Wie groß ist die Menge
A :=
{a T f(n) : a
n
-1
1 (mod n) (°) ,
wobei T f (n) die Funktion der teilerfremden Zahlen zu n ist? Es fällt auf, dass A unter
Multipliktation modulo n abgeschlossen ist. Dies lässt sich leicht einsehen, denn sind
a, b
A, so gilt
11
(a
· b)
n
-1
= a
n
-1
· b
n
-1
1 · 1 = 1 (mod n) ,
so ist auch a
· b (mod n) ein Element von A. So ist die Voraussetzung des Satzes von
Lagrange erfüllt, der da lautet:
Sei n
2 eine natürliche Zahl. Sei A T f(n) eine nicht-leere Menge
derart, dass für je zwei ( nicht notwendigerweise verschiedene) Elemente k
und l von A auch k
· l (mod n) zu A gehört. Dann teilt die Anzahl #A der
Elemente von A die Zahl (n).
Nun kann man ganz leicht zeigen, dass folgendes Lemma 1 über die Anzahl der Elemente
in A gilt:
Sei n eine zusammengesetzte Zahl und sei A die in (°) definierte Menge. Gibt
es eine Zahl a
T f(n), die nicht zu A gehört, so enthält A höchstens
(n)
2
Elemente.
Nach dem Satz von Lagrange gibt es ein n
N mit (n) = k · #A.
Die Voraussetzung bedeutet, dass k
2 gelten muss, also #A =
(n)
k
(n)
2
.
Das heißt, wenn es eine geeignete Basis a gibt, dann beträgt die Wahrscheinlichkeit, diese
zu finden mindestens
1
2
. Wird gezeigt, dass es keine zusammengesetzte Zahl n gibt, die be-
züglich jeder teilerfremden Basis Pseudoprimzahl ist, ist bewiesen, dass der F
ERMAT
-Test
ein effizienter Monte-Carlo-Algorithmus für Zusammengesetztheit ist. Allerdings gibt es
solche Zahlen doch, die als Carmichaelzahlen bezeichnet werden. 561 = 3
· 11 · 17 ist die
kleinste dieser Art. Darüber hinaus gibt es unendlich viele Carmichaelzahlen. Das heißt,
ziemlich viele Zahlen würden als prim bezeichnet werden, obwohl sie es nicht sind, des-
wegen gibt der Test nie aus, dass es sich bei einer Zahl n definitiv um eine Primzahl
handelt. Auf der anderen Seite können aber mit diesem Test auch sehr große zusammen-
gesetzte Zahlen, wenn es sich nicht um Carmichaelzahlen handelt, als solche erkannt
werden. (vgl. [RW09], Abschnitt 3.3)
2.3.2 Solovay-Strassen-Test
Ein weiterer probabilistischer Primalitätstest stammt von S
OLOVAY
und S
TRASSEN
und
beruht auf zwei Primzahleigenschaften. Zuerst ist da der Eulersche-Satz. Mit diesem Kri-
terium werden alle Zahlen heraus gesiebt, die weder Primzahlen noch Eulersche Pseudo-
primzahlen zur Basis a sind.
12
Ende der Leseprobe aus 43 Seiten
- nach oben
Details
- Arbeit zitieren
- , 2011, Primzahltests: Zwischen Wissenschaft und Schule, Hamburg, Bedey Media GmbH, https://www.bachelor-master-publishing.de/document/297399
Kommentare