Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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.
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:
  • 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:
  • MathSciNet review: 2164112