pseudoprime

A probable-prime which is composite is called a pseudoprime. (At one time all probable primes were called pseudoprimes, but now the terminology has been corrected.) The smallest examples of pseudoprimes for bases 2, 3, 5, and 7 are as follows.

341 = 11.31 is a 2-PRP, (Sarrus 1819)
91 = 7.13 is a 3-PRP,
217 = 7.31 is a 5-PRP and,
25 = 5.5 is a 7-PRP.

It is harder to find examples of composites which are probable primes (or better, strong probable primes) to several bases, but this is always possible [AGP94a].

Let t_n be the least composite that is a strong probable prime for the first n primes. We now know:

t₁ = 23 ^. 89
t₂ = 829 ^. 1657
t₃ = 2251 ^. 11251
t₄ = 151 ^. 751 ^. 28351
t₅ = 6763 ^. 10627 ^. 29947
t₆ = 1303 ^. 16927 ^. 157543
t₇ = 10670053 ^. 32010157
t₈ = 10670053 ^. 32010157
t₉ ≤ 149491 ^. 747451 ^. 34233211
t₁₀ ≤ 149491 ^. 747451 ^. 34233211
t₁₁ ≤ 149491 ^. 747451 ^. 34233211
t₁₂ ≤ 399165290221 ^. 798330580441
t₁₃ ≤ 1287836182261 ^. 2575672364521
t₁₄ ≤ 54786377365501 ^. 109572754731001
t₁₅ ≤ 172157429516701 ^. 344314859033401
t₁₆ ≤ 531099297693901 ^. 1062198595387801
t₁₇ ≤ 531099297693901 ^. 1062198595387801
t₁₈ ≤ 27778299663977101 ^. 55556599327954201
t₁₉ ≤ 27778299663977101 ^. 55556599327954201
t₂₀ > 10³⁶

Knowing t_n gives an efficient primality test for small numbers: all numbers less than t_n which pass SPRP tests fore the first n primes are indeed prime!

Arnault found a 337 digit number which passed strong PRP tests for each of the 46 primes below 200 [Arnault95].

It is interesting to note that in 1950 Lehmer, using the weaker definition aⁿ = a (mod n) for probable/pseudo-prime, discovered 2*73*1103 = 161038 is an even "pseudoprime" base two.

See Also: CarmichaelNumber, PRP, FrobeniusPseudoprime

Related pages (outside of this work)

References:

AGP94a
W. R. Alford, A. Granville and C. Pomerance, On the difficulty of finding reliable witnesses. In "Algorithmic Number Theory, First International Symposium, ANTS-I," L. M. Adleman and M. D. Huang editors, Lecture Notes in Computer Science Vol, 877, Springer-Verlag, Berlin, 1994. pp. 1--16, MR 96d:11136
Arnault95
F. Arnault, "Rabin-Miller primality test: composite numbers which pass it," Math. Comp., 64:209 (1995) 355--361. MR 95c:11152
Jaeschke93
G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926. MR 94d:11004
Pinch2000
R. Pinch, The pseudoprimes up to 10¹³. In "Algorithmic number theory (Leiden, 2000)," Lecture Notes in Comput. Sci. Vol, 1838, Springer-Verlag, 2000. Berlin, pp. 459--473, MR 2002g:11177
Pomerance84
C. Pomerance, Lecture notes on primality testing and factoring (notes by G. M. Gagola Jr.), Notes Vol, 4, Mathematical Association of America, 1984. pp. 34 pages,
PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10⁹," Math. Comp., 35:151 (1980) 1003-1026. MR 82g:10030
Ribenboim95
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995. pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]
Zhang2000
Z. Zhang, "Finding strong pseudoprimes to several bases," Math. Comp., 70:234 (2001) 863--872. MR 2001g:11009 (Abstract available)
Zhang2005a
Z. Zhang, "Finding C₃-strong pseudoprimes," Math. Comp., 74:250 (2005) 1009--1024 (electronic). MR 2114662
Zhang2007
Zhang, Zhenxiang, "Two kinds of strong pseudoprimes up to 10³⁶," Math. Comp., 76:260 (2007) 2095--2107 (electronic). MR2336285
ZT2003
Z. Zhang and M. Tang, "Finding strong pseudoprimes to several bases. II," Math. Comp., 72:244 (2003) 2085--2097 (electronic). http://www.ams.org/journal-getitem?pii=S0025-5718-03-01545-X. MR 2004c:11008 (Abstract available)