Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.98.

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.

 

Finding strong pseudoprimes to several bases
HTML articles powered by AMS MathViewer

by Zhenxiang Zhang PDF
Math. Comp. 70 (2001), 863-872 Request permission

Abstract:

Define $\psi _m$ to be the smallest strong pseudoprime to all the first $m$ prime bases. If we know the exact value of $\psi _m$, we will have, for integers $n<\psi _m$, a deterministic primality testing algorithm which is not only easier to implement but also faster than either the Jacobi sum test or the elliptic curve test. Thanks to Pomerance et al. and Jaeschke, $\psi _m$ are known for $1 \leq m \leq 8$. Upper bounds for $\psi _9,\psi _{10} \text { and } \psi _{11}$ were given by Jaeschke. In this paper we tabulate all strong pseudoprimes (spsp’s) $n<10^{24}$ to the first ten prime bases $2, 3, \cdots , 29,$ which have the form $n=p q$ with $p, q$ odd primes and $q-1=k(p-1), k=2, 3, 4.$ There are in total 44 such numbers, six of which are also spsp(31), and three numbers are spsp’s to both bases 31 and 37. As a result the upper bounds for $\psi _{10}$ and $\psi _{11}$ are lowered from 28- and 29-decimal-digit numbers to 22-decimal-digit numbers, and a 24-decimal-digit upper bound for $\psi _{12}$ is obtained. The main tools used in our methods are the biquadratic residue characters and cubic residue characters. We propose necessary conditions for $n$ to be a strong pseudoprime to one or to several prime bases. Comparisons of effectiveness with both Jaeschke’s and Arnault’s methods are given.
References
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2000): 11Y11, 11A15, 11A51
  • Retrieve articles in all journals with MSC (2000): 11Y11, 11A15, 11A51
Additional Information
  • Zhenxiang Zhang
  • Affiliation: Department of Mathematics, Anhui Normal University, 241000 Wuhu, Anhui, P. R. China; State Key Laboratory of Information Security, Graduate School USTC, 100039 Beijing, P. R. China
  • Email: zhangzhx@mail.ahwhptt.net.cn
  • Received by editor(s): August 1, 1997
  • Received by editor(s) in revised form: June 22, 1998, and May 24, 1999
  • Published electronically: February 17, 2000
  • Additional Notes: Supported by the China State Educational Commission Science Foundation and by NSF of China Grant 10071001.

  • Dedicated: Dedicated to the memory of P. Erdős (1913–1996)
  • © Copyright 2000 American Mathematical Society
  • Journal: Math. Comp. 70 (2001), 863-872
  • MSC (2000): Primary 11Y11, 11A15, 11A51
  • DOI: https://doi.org/10.1090/S0025-5718-00-01215-1
  • MathSciNet review: 1697654