Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A generalization of Miller's primality theorem


Authors: Pedro Berrizbeitia and Aurora Olivieri
Journal: Proc. Amer. Math. Soc. 136 (2008), 3095-3104
MSC (2000): Primary 11Y11
DOI: https://doi.org/10.1090/S0002-9939-08-09303-9
Published electronically: May 7, 2008
MathSciNet review: 2407072
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Agrawal, M., Kayal, N., and Saxena, N. ``Primes in P.'' Preprint, Aug. 6, 2002. http://www.cse.iitk.ac.in/users/manindra/publications.html.
  • 2. Ankeny, N. C. The Annals of Mathematicas, 2nd Ser., Vol. 55, No. 1. (Jan., 1952), pp. 65-72. MR 0045159 (13:538c)
  • 3. Bach, E. Analytic methods in the analysis and design of number-theoric algorithms. ACM Distinguished Dissertations. MIT Press, Cambridge, MA, 1985. MR 807772 (87i:11185)
  • 4. Berrizbeitia, P. Sharpening Primes is in $ P$ for a large family of numbers. Math. Comp. 74 (2005), no. 252, 2043-2059. MR 2164112 (2006e:11191)
  • 5. Berrizbeitia, P., and Berry, T. G. Generalized Strong Pseudoprime Tests and Applications, J. Symbolic Computation 30 (2000), no. 2, 151-160. MR 1777169 (2001f:11201)
  • 6. Grantham, J. A probable prime test with high confidence. J. Number Theory 72 (1988), no. 1, 32-47. MR 1643284 (2000e:11160)
  • 7. Granville, A. 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 (2005k:11011)
  • 8. Miller, G. Riemann's hypothesis and tests for primality. J. Comput. System Sci. 13 (1976), no. 3, 300-317. MR 0480295 (58:470a)
  • 9. Monier, L. Evaluation and comparison of two efficient probabilistic primality testing algorithms. Theoret. Comput. Sci. 12 (1980), no. 1, 97-108. MR 582244 (82a:68078)
  • 10. 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.
  • 11. Rabin, M. O. Probabilistic algorithm for testing primality. J. Number Theory 12 (1980), no. 1, 128-138. MR 566880 (81f:10003)
  • 12. Solovay, R., and Strassen, V. The fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84-85. MR 0429721 (55:2732)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 11Y11

Retrieve articles in all journals with MSC (2000): 11Y11


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

DOI: https://doi.org/10.1090/S0002-9939-08-09303-9
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
Article copyright: © Copyright 2008 American Mathematical Society

American Mathematical Society