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\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 [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

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