Miller's primality test (Q1254264): Difference between revisions

The author presents the following simplification of G. L. Miller's primality criterion [J. Comput. Syst. Sci. 13, 300--317 (1976; Zbl 0349.68025)]. Assume that for every integer \(d\equiv 1\pmod 4\), which is either prime or the product of two primes, the \(L\)-function \(\sum_{k=1}^\infty (k\mid d) k^{-s}\) satisfies the generalized Riemann hypothesis, where \((k\mid d)\) is the Jacobi symbol. Let \(n(>1)\) be an odd integer and write \(n - 1 = 2^tu\) with \(t\) and \(u\) integers and \(u\) odd. Then \(n\) is a prime number if and only if for every prime number \(a <c (\log n)^2\), \(a\ne n\), we have \(a^u \equiv 1\pmod n\) or \(a^{2^ju} \equiv - 1 \pmod n\) for some integer \(j\), \(0 \le j < t\). The \(c\) is some constant which does not depend on \(n\).