Miller's primality test
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\).
- On two theorems of Lenstra
- Recent developments in primality testing
- Simple primality tests
- Approximating rings of integers in number fields
- Sequences of numbers generated by addition in formal groups and new primality and factorization tests
- Divisibility of Fermat quotients
- On the divisibility of Fermat quotients
- Statistical distribution of Fermat quotients
- On the additive energy of the Heilbronn subgroup
- Bounds of multiplicative character sums with Fermat quotients of primes
- The Miller–Rabin test with randomized exponents
- On exponential sums over multiplicative subgroups of medium size
- On the 𝑝-divisibility of Fermat quotients
- Explicit bounds for primes in residue classes
- A RECURSIVE FORMULA CONCERNING THE GREATEST PRIME NUMBER LESS THAN OR EQUAL TO AN ODD NUMBER n
- On the value set of Fermat quotients
- On the Euler-Kronecker constants of global fields and primes with small norms
- Primality testing
- Deterministic factoring with oracles
- Regular primes, non-Wieferich primes, and finite multiple zeta values of level \(N\)
- Pattern formation statistics on Fermat quotients
This page was built for publication: Miller's primality test
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1254264)
