Primzahl

Eine Primzahl ist eine natürliche Zahl größer als 1, die nur durch 1 und durch sich selbst teilbar ist. So sind z.B. die Zahlen 2, 3, 5, 7, 11 Primzahlen, die Zahl 10 jedoch nicht, weil sie außer durch 1 und durch 10 auch noch durch 2 und 5 teilbar ist.

Eine Verallgemeinerung des Begriffs Primzahl auf beliebige Ringe ist der Begriff des Primelementes.

Mit Ausnahme der 2 sind alle Primzahlen ungerade, denn alle geraden Zahlen lassen sich ja durch 2 teilen. Zwei aufeinanderfolgende ungerade Zahlen, die beide Primzahlen sind, heißen Primzahlzwillinge, z.B. 11 und 13.

Jede positive ganze Zahl lässts sich eindeutig als Produkt von Primzahlen darstellen (eindeutige Primfaktorzerlegung). So besteht z.B. die Zahl 1050 aus den Primfaktoren 2 · 3 · 5 · 5 · 7.

Primzahlen spielen eine wichtige Rolle unter anderem in der Kryptologie. Einige Verschlüsselungssysteme basieren darauf, dass man zwar relativ schnell große Primzahlen erzeugen und mit ihnen rechnen kann, dass es aber (noch) kein schnelles Verfahren gibt, um große Zahlen in ihre Primfaktoren zu zerlegen (große Zahlen sind Zahlen mit mehr als hundert Stellen).

Größte Primzahl

Da unendlich viele Primzahlen existieren, gibt es keine größte, wie Euklids Primzahlbeweis zeigt.

Die größte bekannte Primzahl ist $2^{13.466.917}-1$ mit 4.053.946 Stellen. Für den ersten Primzahlbeweis einer Zahl mit mehr als 10 Millionen Stellen hat die Electronic Frontier Foundation einen Preis von 100.000 US-Dollar ausgeschrieben.

Sieb des Eratosthenes

Ein Weg, alle Primzahlen bis zu einer Zahl n zu finden, ist das Sieb des Eratosthenes:

Man listet alle ganzen Zahlen von 2 bis n auf.
Man beginnt mit der ersten Zahl p=2.
Alle Vielfachen von p streicht man.
Nun setzt man p auf die nächste Zahl, die nicht gestrichen ist, und fährt beim dritten Schritt fort.
Die Zahlen, die übrig bleiben, sind Primzahlen.

Dieses Verfahren liefert zwar das korrekte Ergebnis, lässt sich aber noch beschleunigen:

Sobald p größer als die Wurzel von n ist, kann man abbrechen, dennn k-fache von p wurden für k<p bereits früher mit dem p-fachen von k gestrichen, und alle größeren Vielfachen von p sind größer als n.
In der Praxis wird man nur die ungeraden Zahlen ab 3 auflisten. Das kann man aber nur machen, wenn man schon weiß, dass 2 eine Primzahl ist und alle geraden Zahlen durch 2 teilbar sind. Beides ist aber allgemein bekannt.

Bei Zahlen größer als 10 Millionen sind andere Primzahlentests schneller.

Weitere Verfahren zum Nachweis von Primzahlen

Der Fermatsche Primzahltest
Der ARCL-Test ist eine Verbesserung des Fermatschen Primzahltests. Der Name besteht aus den Initialen der Mathematiker L.M.Adleman, R.S.Rumely, H.Cohen und H.W.Lenstra Jr.
Der Lucas-Lehmer-Test zum Prüfen von Mersenne-Primzahlen. Dieses Verfahren ist im Artikel Mersenne-Primzahl beschrieben.
Die AKS-Methode ist ein Primzahltest in Polynomialzeit, der im Jahr 2002 von Manindra Agrawal, Neeraj Kayal und Nitin Saxena gefunden und nach ihnen benannt wurde.

Fragen

Warum ist die 1 keine Primzahl?
- Antwort 1: Weil 1 eine Einheit ist (siehe Primelement).
- Antwort 2: Damit man eine eindeutige Primfaktorenzerlegung bekommt (man hätte sonst beliebig viele 1-Faktoren mit drin).

Ungelöste Fragen rund um Primzahlen

Algorithmus zur Primfaktorzerlegung: Gibt es einen schnellen Algorithmus für die Faktorisierung. Dies ist vor allem für viele Kryptographieverfahren von Bedeutung.
Primzahlzwillinge: Ob es unendlich viele Primzahlzwillinge gibt, ist nicht bekannt.
Goldbachsche Vermutung: Kann jede ungerade Zahl größer als 5 als Summe dreier Primzahlen geschrieben werden? bzw. Kann jede gerade Zahl größer als 2 als Summe zweier Primzahlen geschrieben werden?

Spezielle Primzahlen

Weblinks

http://www.primzahlen.de
http://www.utm.edu/research/primes/
http://www.utm.edu/research/primes/howmany.shtml
http://www.mersenne.org/freesoft.htm - Mit GIMPS Primzahlen finden
http://www.informatik.uni-frankfurt.de/~fp/Tools/Sieve.html
http://home.t-online.de/home/0926161717-0002/prgsieb.htm - Visual Basic-Programm zur Berechnung von Primzahlen