Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Sharpening ``Primes is in P'' for a large family of numbers

Author: Pedro Berrizbeitia
Journal: Math. Comp. 74 (2005), 2043-2059
MSC (2000): Primary 11Y11, 11Y16
Published electronically: April 11, 2005
MathSciNet review: 2164112
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We present algorithms that are deterministic primality tests for a large family of integers, namely, integers $n \equiv 1\pmod4$ for which an integer $a$ is given such that the Jacobi symbol $(\frac{a}{n})= -1$, and integers $n \equiv {-1} \pmod 4$ for which an integer $a$ is given such that $(\frac{a}{n})= (\frac{1-a}{n})=-1$. The algorithms we present run in $2^{-\min(k,[2 \log \log n])} \tilde{O}((\log n)^6)$ time, where $k = \nu_2(n-1)$ is the exact power of $2$ dividing $n-1$ when $n \equiv 1\pmod 4$ and $k = \nu_2(n+1) $ if $n \equiv -1\pmod4$. The complexity of our algorithms improves up to $\tilde{O}((\log n)^4)$ when $k \geq [2 \log \log n]$. We also give tests for a more general family of numbers and study their complexity.

References [Enhancements On Off] (What's this?)

  • 1. L. M. Adleman and M.-D. Huang, Primality testing and two dimensional Abelian varieties over finite fields. Lecture Notes in Mathematics, 1512, 1992. MR 1176511 (93g:11128)
  • 2. L. M. Adleman, C. Pomerance, and R. S. Rumely. On distinguishing prime numbers from composite numbers.
    Ann. Math., 117:173-206, 1983. MR 0683806 (84e:10008)
  • 3. M. Agrawal, N. Kayal, and N. Saxena, Primes is in P, preprint, August 2002, posted in
  • 4. A. O. L. Atkin. Lecture notes of a conference, Boulder (Colorado). Manuscript, August 1986.
  • 5. Daniel J. Bernstein, An Exposition of the Agrawal-Kayal-Saxena Primality-Proving Theorem, preprint, August 2002, posted in $\textnormal{html}^\char93 $aks
  • 6. P. Berrizbeitia and T. G. Berry. Biquadratic Reciprocity and a Lucasian Primality Test. Math. Comp. 73: 1559-1564, 2004. MR 2047101
  • 7. P. Berrizbeitia, T. G. Berry, and J. Tena-Ayuso. A Generalization of the Proth Theorem. Acta Arith. 110: 107-115, 2003. MR 2008078 (2004g:11003)
  • 8. H. Cohen and H. W. Lenstra, Jr. Primality testing and Jacobi sums. Math. Comp., 42:297-330, 1984. MR 0726006 (86g:11078)
  • 9. R. Crandall and C. Pomerance. Prime Numbers. A Computational Perspective. Springer-Verlag, New York, Inc., 2001. MR 1821158 (2002a:11007)
  • 10. W. J. Feller. An introduction to probability theory and its applications, vol. 1, John Wiley (1st ed. 1950). MR 0038583 (12:424a)
  • 11. S. Goldwasser and J. Kilian. Almost all primes can be quickly certified. Proceedings of Annual IEEE Symposium on Foundations of Computer Science, pages 316-329, 1986.
  • 12. K. Ireland and M. Rosen. A Classical Introduction to Modern Number Theory. Springer-Verlag, Berlin and New York, 2nd edition, 1990. MR 1070716 (92e:11001)
  • 13. S. Konyagin and C. Pomerance. On primes recognizable in deterministic polynomial time. The mathematics of Paul Erdos, R.L.Graham and J. Nesetril, eds., Springer-Verlag, Berlin, pp.176-198, 1996.MR 1425185 (98a:11184)
  • 14. H. Lenstra, Jr. Divisors in Residue Classes. Math. Comp. 42:331-340, 1984.MR 0726007 (85b:11118)
  • 15. E. Lucas. Sur la recherche des grands nombres premiers. Assoc. Francaise p. l'Avanc. des Science. Comptes Rendus, 5:61-68, 1876.
  • 16. F. Proth. Théorèmes sur les nombres premiers. Comptes Rendus Acad. des Sciences, Paris 87:926, 1878.
  • 17. B. L. van der Waerden. Algebra. vol 1. Ungar, 7th edition, 1970.MR 0263582 (41:8187a)
  • 18. H. C. Williams. Édouard Lucas and Primality Testing. Can. Math. Soc. series of monographs and advanced texts. Wiley-Interscience. 1998.MR 1632793 (2000b:11139)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11Y16

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

Additional Information

Pedro Berrizbeitia
Affiliation: Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela

Received by editor(s): February 4, 2003
Received by editor(s) in revised form: June 12, 2004
Published electronically: April 11, 2005
Article copyright: © Copyright 2005 American Mathematical Society

American Mathematical Society