Logo

Primzahlen

Artikel #10263, »Primzahlen«, geschrieben von: Peter Jacobi (93 %) , Markus Schweiß(Red.) (6 %) et al.

Primzahlen, die natürlichen Zahlen, die nur durch 1 und sich selbst teilbar sind, konventionellerweise ohne 1 selber. Die ersten Primzahlen sind somit die Zahlen 2, 3, 5, 7, 11, 13.

Anzeigen

Jede natürliche Zahl lässt sich eindeutig als Produkt von Primzahlen darstellen, dies ist ihre Primfaktorzerlegung.

Bereits Euklid zeigte, dass es unendliche viele Primzahlen gibt. Leonhard Euler zeigte 1737, dass die Summe der Kehrwerte der Primzahlen eine divergente Reihe ist. Zunehmend genauere Aussagen über die Primzahlen gipfelten im riemannschen Primzahlsatz.

Sehr große Primzahlen angeben zu können und die Teiler großer Zahlen zu finden, ist von erheblicher Bedeutung für die Kryptographie. Der Primzahltest von Agrawal, Kayal und Saxena kann die Entscheidung, ob eine Zahl eine Primzahl ist, in Polynomialzeit lösen. Für die kryptographische Praxis bedeutsamer sind aber noch schnellere Tests, die nur stochastischer Natur sind, also mit – sehr kleiner – Wahrscheinlichkeit ein falsches Ergebnis liefern.

Anzeigen