Primzahl
Eine Primzahl ist eine natürliche Zahl, die größer als 1 ist und nur durch 1 oder sich selbst ganzzahlig teilbar ist. Die kleinsten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23 und 29. Wenn man dann in der Menge der natürlichen Zahlen N = {1, 2, 3, ...} immer weiter voranschreitet, werden die Primzahlen immer seltener.
Es gibt jedoch keine größte Primzahl, denn für jede Primzahl p existiert eine Primzahl p', so dass p' größer als p ist. Euklid hat hierzu im vierten Jahrhundert vor Christus einen Widerspruchsbeweis angeführt: Angenommen, es gibt nur endlich viele Primzahlen, dann lässt sich eine weitere Zahl konstruieren, die eine bisher nicht bekannte Primzahl als Teiler hat oder selbst eine Primzahl ist, was einen Widerspruch zur Annahme darstellt. Somit kann eine endliche Menge niemals alle Primzahlen enthalten, also gibt es unendlich viele Primzahl.
Um zu testen, ob eine ganze Zahl n eine Primzahl ist, nehmen wir die Quadratwurzel von n (oder n1/²), dann runden wir diesen Wert auf die nächsthöhere ganze Zahl auf. Das Ergebnis nennen wir m.
Jetzt müssen alle nachfolgenden Quotienten finden:
qm = n / m
q(m-1) = n / (m-1)
q(m-2) = n / (m-2)
q(m-3) = n / (m-3)
. . .
q3 = n / 3
q2 = n / 2
Die Zahl n ist eine Primzahl, wenn keines der oben abgeleitet q's eine ganze Zahle ergibt.
Mit einem Computer kann man extrem große Zahlen testen, um zu sehen, ob sie eine Primzahl sind. Da es aber keine Begrenzung gibt, wie groß eine natürliche Zahl sein kann, gibt es immer einen Punkt, an dem das Testen auf diese Weise zu groß wird. Das ist auch für die leistungsstärksten Supercomputer eine zu große Aufgabe. Viele Algorithmen wurden entwickelt, um immer größere Primzahlen zu finden, doch sie haben alle ihre Schwächen.
Mersenne- und Fermat-Primzahlen
Eine Mersenne-Primzahl ist eine Zahl der Form 2n - 1, wobei n eine Primzahl ist. Die wenigen bekannten Mersenne-Primzahlen beginnen mit n = 2, n = 3, n = 5, n = 7, n = 13, n = 17, n = 19, n = 31, n = 61 und n = 89.
Eine Fermat-Primzahl ist eine Fermatzahl, die auch eine Primzahl ist. Eine Fermatzahl F n hat die Form 2m + 1, wobei m die n-te Potenz von 2 ist (das heißt m = 2n, wobei n eine ganze Zahl ist).
Primzahlen und Kryptographie
Verschlüsselung folgt immer einer Grundregel: Der Algorithmus (das eigentliche Verfahren) muss nicht geheim gehalten werden, aber der Schlüssel schon. Selbst der anspruchsvollste Hacker der Welt wird nicht in der Lage sein, Daten zu entschlüsseln, solange der Schlüssel geheim bleibt - und Primzahlen sind sehr nützlich, um Schlüssel zu erstellen.
Zum Beispiel liegt die Stärke der Public-/Private-Key-Verschlüsselung darin, dass es einfach ist, das Produkt aus zwei zufällig ausgewählten Primzahlen zu berechnen, aber es kann sehr schwierig und zeitaufwendig sein zu bestimmen, welche zwei Primzahlen verwendet wurden, um ein extrem großes Produkt zu erstellen, wenn nur das Produkt bekannt ist.
In der RSA (Rivest-Shamir-Adleman) Public-Key-Kryptographie sollen Primzahlen immer eindeutig sein. Die vom Diffie-Hellman-Schlüsselaustausch und dem Digital Signature Standard (DSS) verwendeten Primzahlen sind jedoch häufig standardisiert und werden von einer Vielzahl von Anwendungen verwendet.
In der RSA (Rivest-Shamir-Adleman) Public-Key-Kryptographie sollen Primzahlen immer eindeutig sein. Die vom Diffie-Hellman-Schlüsselaustausch und dem Digital Signature Standard (DSS) verwendeten Primzahlen sind jedoch häufig standardisiert und werden von einer Vielzahl von Anwendungen verwendet.
