Home
Search Site
Largest
Finding
How Many?
Mersenne
Glossary
Prime Curios!
email list
FAQ
Prime Lists
Titans
Submit primes

This is the Prime Pages'
interface to our BibTeX database. Rather than being an exhaustive database,
it just lists the references we cite on these pages. Please let me know of any errors you notice.References: [ Home  Author index  Key index  Search ]
 ZT2003
 Z. Zhang and M. Tang, "Finding strong pseudoprimes to several bases. II," Math. Comp., 72:244 (2003) 20852097 (electronic). http://www.ams.org/journalgetitem?pii=S002557180301545X. MR 2004c:11008
Abstract:
Define ψ_{m} to be the smallest strong pseudoprime to all the first m prime bases. If we know the exact value of ψ_{m}, we will have, for integers n<ψ_{m}, a deterministic efficient primality testing algorithm which is easy to implement. Thanks to Pomerance et al. and Jaeschke, the ψ_{m} are known for 1 < m < 8. Upper bounds for ψ_{9},ψ_{10} and ψ_{11} were first given by Jaeschke, and those for ψ_{10} and ψ_{11} were then sharpened by the first author in his previous paper (Math. Comp. 70 (2001), 863872). In this paper, we first follow the first author's previous work to use biquadratic residue characters and cubic residue characters as main tools to tabulate all strong pseudoprimes (spsp's) n<10^{24} to the first five or six prime bases, which have the form n=p q with p, q odd primes and q1=k(p1), k=4/3, 5/2, 3/2, 6; then we tabulate all Carmichael numbers <10^{20}, to the first six prime bases up to 13, which have the form n=q_{1} q_{2} q_{3} with each prime factor q_{i}≡ 3mod 4. There are in total 36 such Carmichael numbers, 12 numbers of which are also spsp's to base 17; 5 numbers are spsp's to bases 17 and 19; one number is an spsp to the first 11 prime bases up to 31. As a result the upper bounds for ψ_{9}, ψ_{10} and ψ_{11} are lowered from 20 and 22decimaldigit numbers to a 19decimaldigit number: ψ_{9}< ψ_{10}< ψ_{11}< Q_{11} &=3825 12305 65464 13051 (19 digits) = 149491· 747451· 34233211. We conjecture that ψ_{9}= ψ_{10}= ψ_{11}=3825 12305 65464 13051, and give reasons to support this conjecture. The main idea for finding these Carmichael numbers is that we loop on the largest prime factor q_{3} and propose necessary conditions on n to be a strong pseudoprime to the first 5 prime bases. Comparisons of effectiveness with Arnault's, Bleichenbacher's, Jaeschke's, and Pinch's methods for finding (Carmichael) numbers with three prime factors, which are strong pseudoprimes to the first several prime bases, are given.
