A generalization of Miller’s primality theorem

Berrizbeitia, Pedro; Olivieri, Aurora

doi:10.1090/S0002-9939-08-09303-9

A generalization of Miller’s primality theorem
HTML articles powered by AMS MathViewer

by Pedro Berrizbeitia and Aurora Olivieri PDF

Proc. Amer. Math. Soc. 136 (2008), 3095-3104 Request permission

Abstract:

For any integer $r$ we show that the notion of $\omega$-prime to base $a$ introduced by Berrizbeitia and Berry, 2000, leads to a primality test for numbers $n$ congruent to $1$ modulo $r$, which runs in polynomial time assuming the Extended Riemann Hypothesis (ERH). For $r = 2$ we obtain Miller’s classical result.

References

Agrawal, M., Kayal, N., and Saxena, N. “Primes in P.” Preprint, Aug. 6, 2002. http://www.cse.iitk.ac.in/users/manindra/publications.html.
N. C. Ankeny, The least quadratic non residue, Ann. of Math. (2) 55 (1952), 65–72. MR 45159, DOI 10.2307/1969420
Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772
Pedro Berrizbeitia, Sharpening “PRIMES is in $P$” for a large family of numbers, Math. Comp. 74 (2005), no. 252, 2043–2059. MR 2164112, DOI 10.1090/S0025-5718-05-01727-8
Pedro Berrizbeitia and T. G. Berry, Generalized strong pseudoprime tests and applications, J. Symbolic Comput. 30 (2000), no. 2, 151–160. MR 1777169, DOI 10.1006/jsco.1999.0343
Jon Grantham, A probable prime test with high confidence, J. Number Theory 72 (1998), no. 1, 32–47. MR 1643284, DOI 10.1006/jnth.1998.2247
Andrew Granville, It is easy to determine whether a given integer is prime, Bull. Amer. Math. Soc. (N.S.) 42 (2005), no. 1, 3–38. MR 2115065, DOI 10.1090/S0273-0979-04-01037-7
Gary L. Miller, Riemann’s hypothesis and tests for primality, J. Comput. System Sci. 13 (1976), no. 3, 300–317. MR 480295, DOI 10.1016/S0022-0000(76)80043-8
Louis Monier, Evaluation and comparison of two efficient probabilistic primality testing algorithms, Theoret. Comput. Sci. 12 (1980), no. 1, 97–108. MR 582244, DOI 10.1016/0304-3975(80)90007-9
Pocklington, H. C. The Determination of the Prime or Composite Nature of Large Numbers by Fermat’s Theorem. Proc. Cambridge Phil. Soc. 18, 29-30, 1914.
Michael O. Rabin, Probabilistic algorithm for testing primality, J. Number Theory 12 (1980), no. 1, 128–138. MR 566880, DOI 10.1016/0022-314X(80)90084-0
R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, DOI 10.1137/0206006