|
A generalization of Miller's primality theorem
Author(s):
Pedro
Berrizbeitia;
Aurora
Olivieri
Journal:
Proc. Amer. Math. Soc.
136
(2008),
3095-3104.
MSC (2000):
Primary 11Y11
Posted:
May 7, 2008
Retrieve article in:
PDF DVI PostScript
Abstract |
References |
Similar articles |
Additional information
Abstract:
For any integer  we show that the notion of  -prime to base  introduced by Berrizbeitia and Berry, 2000, leads to a primality test for numbers  congruent to  modulo  , which runs in polynomial time assuming the Extended Riemann Hypothesis (ERH). For  we obtain Miller's classical result.
References:
-
- 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
 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:
10.1090/S0002-9939-08-09303-9
PII:
S 0002-9939(08)09303-9
Received by editor(s):
April 24, 2007,
Received by editor(s) in revised form:
August 15, 2007
Posted:
May 7, 2008
Communicated by:
Ken Ono
Copyright of article:
Copyright
2008,
American Mathematical Society
|
Comments: webmaster@ams.org