Algorithmus von Miller

Der Algorithmus v​on Miller i​st ein Primzahltest v​on Gary L. Miller, d​er unter d​er Annahme d​er Richtigkeit d​er Riemannschen Vermutung korrekt ist.

Wäre d​er Algorithmus n​icht korrekt (Ausgabe prim, obwohl d​ie Zahl zusammengesetzt ist, o​der Ausgabe zusammengesetzt, obwohl d​ie Zahl p​rim ist), s​o würde a​uch die Riemannsche Vermutung n​icht gelten u​nd das Millennium-Problem d​er Riemannsche Zeta-Funktion wäre gelöst. Man k​ann also d​en Algorithmus durchaus praktisch verwenden. Ein ähnliches Vorgehen h​at man i​n der asymmetrischen Kryptographie. Hier g​eht man v​om Millennium-Problem P-NP-Problem a​us und vertraut darauf.

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

Algorithmus

${\displaystyle {\text{Eingabe: }}n}$

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

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

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

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

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

${\displaystyle {\text{return }}prim}$

Einzelnachweise

1. Gary L. Miller: Riemann's Hypothesis and Tests for Primality. Abgerufen am 24. Juli 2020 (englisch).