## Sharpening “Primes is in P” for a large family of numbers

HTML articles powered by AMS MathViewer

- by Pedro Berrizbeitia PDF
- Math. Comp.
**74**(2005), 2043-2059 Request permission

## Abstract:

We present algorithms that are deterministic primality tests for a large family of integers, namely, integers $n \equiv 1\pmod 4$ 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\pmod 4$. 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

- Leonard M. Adleman and Ming-Deh A. Huang,
*Primality testing and abelian varieties over finite fields*, Lecture Notes in Mathematics, vol. 1512, Springer-Verlag, Berlin, 1992. MR**1176511**, DOI 10.1007/BFb0090185 - Leonard M. Adleman, Carl Pomerance, and Robert S. Rumely,
*On distinguishing prime numbers from composite numbers*, Ann. of Math. (2)**117**(1983), no. 1, 173–206. MR**683806**, DOI 10.2307/2006975 - M. Agrawal, N. Kayal, and N. Saxena,
*Primes is in P*, preprint, August 2002, posted in http://www.cse.iitk.ac.in/news/primality.html - A. O. L. Atkin.
*Lecture notes of a conference*, Boulder (Colorado). Manuscript, August 1986. - Daniel J. Bernstein,
*An Exposition of the Agrawal-Kayal-Saxena Primality-Proving Theorem*, preprint, August 2002, posted in http://cr.yp.to/papers.html\#aks - Pedro Berrizbeitia and T. G. Berry,
*Biquadratic reciprocity and a Lucasian primality test*, Math. Comp.**73**(2004), no. 247, 1559–1564. MR**2047101**, DOI 10.1090/S0025-5718-03-01575-8 - Pedro Berrizbeitia, T. G. Berry, and Juan Tena-Ayuso,
*A generalization of Proth’s theorem*, Acta Arith.**110**(2003), no. 2, 107–115. MR**2008078**, DOI 10.4064/aa110-2-1 - H. Cohen and H. W. Lenstra Jr.,
*Primality testing and Jacobi sums*, Math. Comp.**42**(1984), no. 165, 297–330. MR**726006**, DOI 10.1090/S0025-5718-1984-0726006-X - Richard Crandall and Carl Pomerance,
*Prime numbers*, Springer-Verlag, New York, 2001. A computational perspective. MR**1821158**, DOI 10.1007/978-1-4684-9316-0 - William Feller,
*An Introduction to Probability Theory and Its Applications. Vol. I*, John Wiley & Sons, Inc., New York, N.Y., 1950. MR**0038583** - 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. - Kenneth Ireland and Michael Rosen,
*A classical introduction to modern number theory*, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR**1070716**, DOI 10.1007/978-1-4757-2103-4 - Sergei Konyagin and Carl Pomerance,
*On primes recognizable in deterministic polynomial time*, The mathematics of Paul Erdős, I, Algorithms Combin., vol. 13, Springer, Berlin, 1997, pp. 176–198. MR**1425185**, DOI 10.1007/978-3-642-60408-9_{1}5 - H. W. Lenstra Jr.,
*Divisors in residue classes*, Math. Comp.**42**(1984), no. 165, 331–340. MR**726007**, DOI 10.1090/S0025-5718-1984-0726007-1 - E. Lucas.
*Sur la recherche des grands nombres premiers*. Assoc. Francaise p. l’Avanc. des Science. Comptes Rendus, 5:61-68, 1876. - F. Proth.
*Théorèmes sur les nombres premiers*. Comptes Rendus Acad. des Sciences, Paris 87:926, 1878. - B. L. van der Waerden,
*Algebra. Vol 1*, Frederick Ungar Publishing Co., New York, 1970. Translated by Fred Blum and John R. Schulenberger. MR**0263582** - Hugh C. Williams,
*Édouard Lucas and primality testing*, Canadian Mathematical Society Series of Monographs and Advanced Texts, vol. 22, John Wiley & Sons, Inc., New York, 1998. A Wiley-Interscience Publication. MR**1632793**

## Additional Information

**Pedro Berrizbeitia**- Affiliation: Departamento de Matemáticas Puras y Aplicadas, Universidad Simón Bolívar, Caracas, Venezuela
- Email: pedrob@usb.ve
- Received by editor(s): February 4, 2003
- Received by editor(s) in revised form: June 12, 2004
- Published electronically: April 11, 2005
- © Copyright 2005 American Mathematical Society
- Journal: Math. Comp.
**74**(2005), 2043-2059 - MSC (2000): Primary 11Y11, 11Y16
- DOI: https://doi.org/10.1090/S0025-5718-05-01727-8
- MathSciNet review: 2164112