Algorithmus von Miller

Der Algorithmus von Miller ist ein Primzahltest von Gary L. Miller, der unter der Annahme der Richtigkeit der Riemannschen Vermutung korrekt ist.

Wäre der Algorithmus nicht korrekt (Ausgabe prim, obwohl die Zahl zusammengesetzt ist, oder Ausgabe zusammengesetzt, obwohl die Zahl prim ist), so würde auch die Riemannsche Vermutung nicht gelten und das Millennium-Problem der Riemannsche Zeta-Funktion wäre gelöst. Man kann also den Algorithmus durchaus praktisch verwenden. Ein ähnliches Vorgehen hat man in der asymmetrischen Kryptographie. Hier geht man vom Millennium-Problem P-NP-Problem aus und vertraut darauf.

Miller veröffentlichte diesen Algorithmus sowie seine Korrektheit in seiner Dissertation 1975 Riemann's Hypothesis and Tests for Primality. Im Gegensatz zum Miller-Rabin-Test ist dieser Algorithmus deterministisch und nicht probabilistisch.

Algorithmus

${\text{Eingabe: }}n$

${\text{Sei }}n-1=2^{e}\cdot m{\text{ sodass }}m{\text{ ungerade }}$

${\text{FOR }}b:=2{\text{ TO }}2(\ln n)^{2}{\text{ DO}}$

• ${\text{berechne }}v=(b^{m},b^{2m},b^{4m},...,b^{n-1})$

• ${\text{IF }}v=(1,1,...1){\text{ or }}v=(x,...,-1,1,...1)$ ${\text{THEN next }}b$

• ${\text{IF }}v=(x,...,y,1,...,1){\text{ or }}v=(...,x+1)$ ${\text{THEN return }}zusammengesetzt$

${\text{return }}prim$