Primzahlgenerator

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Als Primzahlgenerator bezeichnet man in der Informatik einen Algorithmus , sodass für natürliche Zahlen der Wert die -te Primzahl ist. In der Mathematik und speziell der Zahlentheorie entspricht das Formeln, die besonders viele Primzahlen liefern (Formeln für Primzahlen). Bisher wurde noch kein effizienter Primzahlgenerator gefunden, insbesondere existiert keine praktikable geschlossene Formel zur Generierung von Primzahlen.

Es gibt allerdings Formeln, bei denen eine gewisse Wahrscheinlichkeit besteht, dass die erzeugten Zahlen eine Primzahl sein könnten. Trotzdem müssen die erzeugten Zahlen auf ihre Eigenschaft als Primzahl getestet werden. Im Artikel werden auch andere Formeln behandelt, die nicht praxistauglich sind, die aber in der mathematischen Literatur bezüglich der Frage diskutiert wurden ob sie viele Primzahlen liefern.

Geschichte[Bearbeiten | Quelltext bearbeiten]

Einer der ältesten Algorithmen zur Bestimmung von Primzahlen ist das Sieb des Eratosthenes, bei dem nacheinander aus einer Liste der natürlichen Zahlen diejenigen Zahlen gestrichen werden, die Vielfache der jeweils kleinsten noch nicht gestrichenen Zahl sind. Dadurch bleiben die Primzahlen innerhalb der Ausgangsliste übrig.

Schon Euler gab die Formeln und an, die für bzw. Primzahlen liefern. Auch für größere Werte von liefern die beiden Formeln viele Primzahlen, weil das Ergebnis nie durch Primzahlen bzw. ganzzahlig teilbar ist. Allgemein gibt es viele solche Formeln , wodurch sich die auffällige Ulam-Spirale erklärt. Es gibt aber nach Adrien-Marie Legendre kein Polynom, das für alle Werte der Variablen in den natürlichen Zahlen Primzahlen ergibt (auch nicht fast alle Primzahlen). Die Frage welche ganzzahligen Polynome unendlich viele Primzahlen erzeugen ist Gegenstand der Bunjakowski-Vermutung.

Die beliebteste ist die der Mersenne-Zahl , bei der eine Primzahl ist. Durch die besonderen Eigenschaften der Teiler von Mersenne-Zahlen eignen sie sich für die Suche nach möglichst großen Primzahlen.

Fermat vermutete, dass alle Zahlen der Form prim sind; man nennt sie Fermat-Zahlen. Tatsächlich ist aber für keine derartige Primzahl bekannt.

Auch bekannt ist eine Anwendung des Satzes von Euklid, bei der zum Primorial (Produkt aller Primzahlen von 2 bis ) eine 1 addiert wird:

ist prim für (Folge A005234 in OEIS) Es ist unbekannt ob es unendlich viele Primzahlen gibt, die so erzeugt werden.

Weitere Formeln[Bearbeiten | Quelltext bearbeiten]

  • ist prim für (Folge A002982 in OEIS)
  • ist prim für (Folge A002981 in OEIS)
  • Primzahlen der Form sind: (Folge A049536 in OEIS)

Nach dem Dirichletschen Primzahlsatz enthält eine arithmetische Folge (wobei , prim zueinander sind und die natürlichen Zahlen durchläuft) unendlich viele Primzahlen (allerdings auch zusammengesetzte Zahlen). Allerdings gibt es nach Green und Terence Tao für jedes arithmetische Folgen (festgelegt durch a,b) die Primzahlen für aufeinanderfolgende Werte liefern. Zum Beispiel liefert:

Primzahlen für . Die Methode entspricht dem Fall linearer Polynome.

Trivialer Generator[Bearbeiten | Quelltext bearbeiten]

Ein trivialer Primzahlgenerator kann folgendermaßen induktiv definiert werden:

  1. für ist die auf folgende Primzahl, wobei einfach alle Zahlen ab aufsteigend darauf getestet werden, ob sie eine Primzahl sind.

Dieses Verfahren ist aber recht ineffektiv, da nacheinander alle ungeraden natürlichen Zahlen getestet werden müssen. Als Alternative bietet es sich an, mittels einer Siebmethode, z. B. Sieb des Eratosthenes oder Sieb von Atkin, eine genügend lange Liste von Primzahlen zu erstellen und diese dann bis zur gewünschten Primzahl zu durchlaufen. Dabei bestimmt man manchmal zunächst Primzahl-ähnliche Mengen (Fastprimzahlen).

Satz von Wilson[Bearbeiten | Quelltext bearbeiten]

Eine nicht sehr praktikable Formel für alle Primzahlen beruht auf dem Satz von Wilson. Die Formel lautet unter Verwendung der Abrundungsfunktion:

, für natürliche Zahlen .

Nach dem Satz von Wilson ist prim genau dann falls . Daraus folgt dass die Formel nur Primzahlen liefert und jede Primzahl außer 2 genau einmal. Denn ist prim, so ist und . Ist nicht prim, so ist und

Diophantische Mengen für Primzahlen[Bearbeiten | Quelltext bearbeiten]

Nach den Arbeiten zum Hilberts zehntem Problem gibt es ein System von endlich vielen diophantischen Gleichungen (Polynomen über den ganzen Zahlen), die als Lösung alle Primzahlen und nur diese haben. Nach Juri Wladimirowitsch Matijassewitsch sollte es solch ein System mit neun oder weniger Variablen geben. James P. Jones und Kollegen gaben 1976 ein System von 14 Polynomen in 26 Variablen an.[1] Explizit besteht das System aus den Gleichungen:

mit den Variablen . Dann und nur dann, wenn eine Lösung in natürlichen Zahlen existiert ist die Variable eine Primzahl.

Das lässt sich auch in eine Ungleichung zusammenfassen:

Wenn man für die einzelnen Variablen natürliche Zahlen einsetzt sind genau dann Primzahlen wenn die Ungleichung erfüllt ist.

Es gibt auch ein die Primzahlen (und nur diese) erzeugendes System von n diophantischen Gleichungen mit nur zehn Variablen, allerdings mit sehr hohem Grad (in der Größenordnung ). Nach Thoralf Skolem kann man auch immer ein solches System mit nur Polynomen höchstens vierten Grades finden, allerdings ist in diesem Fall die Zahl der Variablen sehr hoch (mindestens 58 so weit bekannt).[2] Die Methoden sind bisher von keinem praktischen Nutzen.

Formel von Mills[Bearbeiten | Quelltext bearbeiten]

W. H. Mills zeigte 1947,[3] dass es eine reelle Zahl gibt,

so dass

für alle natürlichen Zahlen prim ist. Man kann unter Annahme der Riemannschen Vermutung zeigen, dass das kleinste solche (die sogenannte Mill'sche Konstante) einen Wert von etwa hat.[4] Die mit der Formel erzeugten Primzahlen heissen Mills-Primzahlen: , , Da über aber wenig bekannt ist (noch nicht einmal ob die Konstante rational oder irrational ist), hat die Formel wenig praktischen Wert.

Formel von Wright[Bearbeiten | Quelltext bearbeiten]

Eine ähnliche Formel wie die von Mills fand E. M. Wright.[5] Wright zeigte dass es eine reelle Zahl gibt so dass

prim ist für alle .

Dabei ist rekursiv definiert:

, für ,

Wright gab auch die ersten Dezimalstellen von als . Das ergibt die Primzahlen , , und . Dagegen ist mit diesem Wert von gerade und man braucht für die folgenden Primzahlen mehr Dezimalstellen. Da die Formel auf der Kenntnis von beruht ist sie praktisch ebenso nutzlos wie die von Mills.

Conways Primzahlgenerator[Bearbeiten | Quelltext bearbeiten]

Für die Primzahl-erzeugende Maschine (PRIMEGAME) von John Horton Conway[6] siehe FRACTRAN. Die Methode ist allerdings ebenfalls nicht praktikabel zur Generierung von Primzahllisten.

Primzahlgenerator für endliche Primzahlmengen[Bearbeiten | Quelltext bearbeiten]

Ross Honsberger[7] gibt einen einfachen Beweis für folgenden Satz:

Man teile die ersten Primzahlen beliebig auf zwei disjunkte Mengen auf, so dass . Dann sei das Produkt der Elemente von und das der Elemente von . darf auch leer sein, dann ist (leeres Produkt). Falls nun , dann ist eine Primzahl, und ist prim, wenn .

Beispiel: (betrachtet werden dann nur Zahlen kleiner ):

.

Zweites Beispiel: (betrachtet werden dann nur Zahlen kleiner ):

.

Jedoch sind

größergleich 169 und nicht prim.

Weblinks[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. James P. Jones, Daihachiro Sato, Hideo Wada, Douglas Wiens, Diophantine representation of the set of prime numbers, American Mathematical Monthly, Band 83, 1976, S. 449–464
  2. James P. Jones, Universal diophantine equation, Journal of Symbolic Logic, Band 47, 1982, S. 549–571
  3. Mills, A prime-representing function, Bulletin of the AMS, Band 53, 1947, S. 604
  4. OEIS, A 051021
  5. E. M. Wright, A prime-representing function, American Mathematical Monthly, Band 58, 1951, S. 616–618
  6. Richard K. Guy, Conway's Prime Producing Machine, Mathematics Magazine, Band 56, 1983, S. 26–33
  7. Honsberger, More Mathematical Morsels, Mathematical Association of America 1991, S. 108 (Morsel 20)