Die natürlichen Zahlen der Reihe nach aufzuschreiben. Die 1 wird gestrichen.

Die 2 wird als Primzahl gekennzeichnet. Nun wird jede 2te Zahl (durch 2 teilbare Zahl, also gerade Zahl) gestrichen.

Die nächste ungestrichenen Zahl ist die 3, sie ist ebenfalls eine Primzahl. Jetzt wird jede dritte Zahl nach der 3 gestrichen, wobei auch bereits gestrichene Zahlen mitgezählt werden.

So zeigt sich, dass die 5 die nächste ungestrichene Zahl, ebenfalls Primzahl ist. Mit ihr wird das Verfahren fortgesetzt.

Die relative Häufigkeit der Primzahlen in einem Intervall von 1 bis x wird jedoch um so kleiner, je größer x wird. Man könnte also sagen die Primzahldichte wird mit wachsendem x immer geringer. Die Anzahl der Primzahlen unterhalb von einer Grenze x lässt sich jedoch Abschätzen.

Primzahlsatz:

Schon früh haben Mathematiker versucht eine Funktion zu finden, deren Wertebereich eine möglichst große Teilmenge der Primzahlen darstellt. Noch wurde keine Funktion gefunden, deren Wertebereich nur Primzahlen erhält. Jedoch wurde erkannt, dass manche Primzahlen von einer ganz bestimmten Form sind.

Primzahlen, die eine der beiden Formen annehmen gehören dann zu der Familie der Mersennschen bzw. Fermatschen Primzahlen.

Zwei ganze Zahlen heißen kongruent modulo n (in Zeichen a = b mod n), wenn bei der Division der beiden Zahlen a und b durch n derselbe Rest bleibt oder, anders ausgedrückt, wenn n ein Teiler von a - b ist.

Bsp.: 4 =10 mod 3, denn 4 : 3 = 1 Rest 1

und 10 : 3 = 3 Rest 1 .

und 10 - 4 = 6 (teilbar durch 3)

Beide Zahlen haben den gleichen Rest (hier 1), ihre Differenz ist Teilbar durch n (hier 3 ) ohne dass ein Rest entsteht.

Als Reste bei der Division durch eine beliebige Zahl n treten die Zahlen 0, 1, ..., n-1 auf.

Für die Restklassen sind die Addition, die Subtraktion und die Multiplikation eindeutig definiert. Ebenso gelten das Assoziativgesetz, das Kommutativgesetz und das Distributivgesetz.

Jede Zahl, die keine Primzahl ist, lässt sich als Produkt von Primzahlen darstellen.

Bsp.: 30 = 2 * 3 * 5

Theoretisch lässt sich nun jede beliebig große Zahle in ihre Primfaktoren zerlegen. Dafür muß im Grunde nur jede Primzahl, die kleiner oder gleich Wurzel(n) ist, auf ihre Eigenschaft als Teiler geprüft werden.

Allerdings beinhaltet dieses eigentlich einfache Verfahren einen sehr großen Rechenaufwand, wenn die Zahlen, die zu prüfen sind, sehr groß werden. Bei einer Zahl in der Größenordnung von 10^100 müßte ein Rechner im ungünstigen Fall ca. 8 * 10^47 Primzahlen auf ihre Teilereigenschaft testen. Für dieses Vorhaben bräuchte selbst ein Großrechner eine Rechenzeit von 10^28 Jahren (was das Alter des Weltalls überträfe).

Die Sicherheit des RSA-Verschlüsselungssystem beruht auf genau diesem Phänomen.

Es existieren zwar verschiedene Algorithmen, die eine leichte Verbesserung des "naiven Probierverfahrens" darstellen, diese stellen allerdings für wirklich große Zahlen noch keine wesentliche Verkürzung der Rechenzeit dar.

Als Maß für die Dauer des Rechenvorgangs kann die Anzahl der elementaren Rechenoperationen, die zur Ausführung eines Algorithmus erforderlich sind, angesehen werden. Unter einer elementaren Rechenoperation wird die Addition, die Subtraktion, die Multiplikation oder die Division von Zahlen des vom Computer verarbeiteten Standardformats verstanden.

Die Anzahl der nötigen Rechenoperationen lässt sich durch folgende Formel abschätzen:

const * (ln n)²

Da bei der Rechenzeit in erster Linie die Anzahl der Rechenoperationen im Bezug auf die Änderung von n ausschlaggebend sind, ist der exakte Wert der Konstante uninteressant.

Man unterscheidet zwei Arten von Algorithmen:

1) Algorithmen mit polynomialem Verhalten:

2) Algorithmen mit nicht polynomialem Verhalten:

Alle bis heute bekannten Algorithmen zur Faktorisierung einer natürlichen Zahl zeigen nicht-polynominales Verhalten.

Das RSA - Verfahren beruht auf der Schwierigkeit, große Zahlen in Primfaktoren zu zerlegen.

Ein Produkt aus zwei großen Primzahlen zu bilden ist für jeden Rechner einfach. Sind diese Primzahlen jedoch nicht bekannt, so ist es sehr schwer sie herauszufinden, da dies die Kapazitäten der Rechner überfordert und eine Rechenzeit von mehreren Jahren erfordern würde. Deswegen werden die Primzahlen nach der Multiplikation sofort vernichtet.

Deswegen ist das RSA - Verfahren eines der sichersten Verschlüsselungsverfahren - bis ein Verfahren zur schnellen Faktorisierung gefunden wird.

Referentin: Tina Scholz,

MSS 13/2,

INF 1, SHM