Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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?)


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
Email: pedrob@usb.ve

DOI: http://dx.doi.org/10.1090/S0025-5718-05-01727-8
PII: S 0025-5718(05)01727-8
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