effizienter Primzahltest

In der Informatik gibt es häufig das Problem, dass man entscheiden muss, ob eine Zahl eine Primzahl ist oder nicht. Zur Erinnerung: Eine Zahl p ist genau dann eine Primzahl, wenn sie nur durch sich selbst oder durch eins (ohne Rest) teilbar ist. Doch wie entscheidet man effizient, ob eine großen Zahl, eine Primzahl ist?

Lösung 1

Der triviale Weg lautet: Teile p durch alle Zahlen z, wobei 1< z < p. Hat eines der Ergebnisse keinen Rest, d.h. p ist durch z* teilbar, so ist p keine Primzahl.

primzahl=true;
for (x=2 to z-1)
  {
  if p mod x = 0 then primzahl=false;
  }
ausgabe primzahl;

Diese Variante ist einfach aber auch höchst ineffizient: Die Laufzeit beträgt im Mittel O(n)=½n = n.

Lösung 2

Eine Verbesserung bring die Abfrage, wenn man die Teilbarkeit nicht bis z-1 testet, sondern nur bis Wurzel: sqr(z-1). Das ist möglich, weil p mod x genau dann null wird, wenn p mod y = 0 und x*y=p.

primzahl=true;
for (x=2 to sqr(z-1))
  {
  if p mod x = 0 then primzahl=false;
  }
ausgabe primzahl;

Diese Variante hat eine mittlere Laufzeit O(n)= ½ * √n= √n

Lösung 3

Die nächste Lösung ist ein probabilistischer Algorithmus, d.h. ein Algorithmus dessen Ergebnis wahrscheinlich, aber nicht 100%ig richtig ist.
Als Ausgangspunkt nehmen wir Fermats Satz: „Für alle Primzahlen n und a ε {1,…,n-1} gilt a^n-1≡ 1 (mod n)“ Leider gilt die Umkehrung von Fermats Satz nicht, aber doch „fast“.

funktion mod_exp(a,b,c) //Hilfsfunktion
  {
  return (a^b mod c);
  }

funktion primzahltest(n)
  {
  if mod_exp(2,n-1,n)=1 then return true else return false;
  }

Dieser Algorithmus ist mit durchnittlich O(n)=1 schon nahezu perfekt, wäre da nicht die Unsicherheit, ob das Ergebnis auch stimmt. Aber wie wahrscheinlich ist eine falsche Ausgabe? Extrem selten!: folgende Fehlerquoten sind bekannt: Sei n eine Zufallszahl mit 50 (100) Stellen, dann ist die Wahrscheinlichkeit p, dass die Zahl fälschlich als Primzahl erkannt wird kleiner als 10^-6 (10^-13). Die Fehlerqute könnte durch (einen/mehrere) Folgetest noch weiter reduziert werden:

funktion primzahltest(n)
  {
  if mod_exp(2,n-1,n)=1 then
    {
    if mod_exp(3,n-1,n)=1 then return true;
    }
  return false;
  }

Die Fehlerwahrscheinlichkeit sinkt so von 10^-6 (10^-13) auf etwa 10^-12 (10^-26).
Hat eine Zahl den Primzahltest bestanden so ist die Wahrscheinlichkeit, dass sich wirklich um eine Primzahl handelt, nahezu 100%. Durch das anhängen anderere probabilistischer Verfahren kann man sich noch weiter den 100% annähern. Um 100% sicher zu sein, führt aktuell kein Weg an Variante 2 vorbei.

Offtopic: Wie findet man eine sehr lange Primzahl?

In der Kryptographie werden oft Primzahlen benötigt die tausende Stellen haben. Folgender Algorithmus findet eine Primzahl:

Repeat
  {
  Nimm zufällig eine n-Stellige Zahl z (z.b. n=1000)
  {
Bis primzahltest(n)=true

Die Annahme, dass es sehr lange dauern könnte, bis man eine solche Zahl findet ist falsch, denn der Primzahlsatz besagt, dass es im Intervall [1-n] etwa n*log(n) primzahlen gibt. D.h. zum finden einer Zahl sind etwa ln(n) Schritte notwendig. Beispiel: für eine 100 Stelligen Zahl sind etwa 230 Schritte notwendig.