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
Additional Information
- Pedro Berrizbeitia
- Affiliation: Departamento de Matemáticas P. y A., Universidad Simón Bolívar, Sartenejas, Caracas 1080-A, Venezuela
- Email: pedrob@usb.ve
- Aurora Olivieri
- Affiliation: Departamento de Matemáticas P. y A., Universidad Simón Bolívar, Sartenejas, Caracas 1080-A, Venezuela
- Email: olivieri@usb.ve
- Received by editor(s): April 24, 2007
- Received by editor(s) in revised form: August 15, 2007
- Published electronically: May 7, 2008
- Communicated by: Ken Ono
- © Copyright 2008 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 136 (2008), 3095-3104
- MSC (2000): Primary 11Y11
- DOI: https://doi.org/10.1090/S0002-9939-08-09303-9
- MathSciNet review: 2407072