Miller's algorithm

The algorithm of Miller is a prime test of Gary L. Miller , of assuming the correctness of the Riemann hypothesis is correct.

If the algorithm were incorrect (output prime, although the number is composite, or output composite, although the number is prime), the Riemann Hypothesis would not hold either and the Millennium problem of the Riemann zeta function would be solved. So you can use the algorithm quite practically. A similar procedure is used in asymmetric cryptography . Here one starts from the Millennium problem P-NP problem and trusts it.

Miller published this algorithm and its correctness in his 1975 dissertation, Riemann's Hypothesis and Tests for Primality . In contrast to the Miller-Rabin test , this algorithm is deterministic and not probabilistic .

algorithm

${\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}$

Individual evidence

1. ^ Gary L. Miller: Riemann's Hypothesis and Tests for Primality. Retrieved July 24, 2020 .