Strong Pseudoprime

A strong pseudoprime to an integer base is an odd composite number with (for an odd positive integer and a positive integer ) for which either

(1)

or

(2)

for some , 1, ..., (Riesel 1994, p. 91). Note that Guy (1994, p. 27) restricts the definition of strong pseudoprimes to only those satisfying (1).

The definition is motivated by the fact that a Fermat pseudoprime to the base satisfies

(3)

But since is odd, it can be written , and

(4)

If is prime, it must divide at least one of the factors, but can't divide both because it would then divide their difference

(5)

Therefore,

(6)

so write to obtain

(7)

If divides exactly one of these factors but is composite, it is a strong pseudoprime. An odd composite number is a strong pseudoprime to at most 1/4 of the integer bases , 2, ..., (Monier 1980, Rabin 1980). The strong pseudoprimes provide the basis for Miller's primality test and Rabin-Miller strong pseudoprime test.

A strong pseudoprime to the base is also an Euler pseudoprime to the base (Pomerance et al. 1980). The strong pseudoprimes include some Euler pseudoprimes, Fermat pseudoprimes, and Carmichael numbers.

The following table lists the first few pseudoprimes to a number of small bases.

	OEIS	-strong pseudoprimes
2	A001262	2047, 3277, 4033, 4681, 8321, ...
3	A020229	121, 703, 1891, 3281, 8401, 8911, ...
4	A020230	341, 1387, 2047, 3277, 4033, 4371, ...
5	A020231	781, 1541, 5461, 5611, 7813, ...
6	A020232	217, 481, 1111, 1261, 2701, ...
7	A020233	25, 325, 703, 2101, 2353, 4525, ...
8	A020234	9, 65, 481, 511, 1417, 2047, ...
9	A020235	91, 121, 671, 703, 1541, 1729, ...

The number of strong 2-pseudoprimes less than , , ... are 0, 5, 16, 46, 162, ... (OEIS A055552). Note that Guy's (1994, p. 27) definition gives only the subset 2047, 4681, 15841, 42799, 52633, 90751, ..., giving counts inconsistent with those in Guy's table.

Exactly 13 odd composite numbers below pass the strong pseudoprime tests to all of the bases 2, 3, and 5. If base 7 is added, then the only such composite number is 3215031751 (Jaeschke 1993, pp. 922-923). Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than , nine if 7 is added, and none if 11 is added. Also, the bases 2, 13, 23, and 1662803 have no exceptions up to .

If is composite, then there is a base for which is not a strong pseudoprime. There are therefore no "strong Carmichael numbers." Let denote the smallest strong pseudoprime to all of the first primes taken as bases (i.e., the smallest odd composite number for which the Rabin-Miller strong pseudoprime test on prime numbers less than or equal to the th prime number fails to reveal compositeness). Jaeschke (1993) computed from to 8 and gave upper bounds for to 11.

			(8)
			(9)
			(10)
			(11)
			(12)
			(13)
			(14)
			(15)
			(16)
			(17)
			(18)
			(19)
			(20)

(OEIS A014233). The values for , , and were initially upper bounds obtained by Zhang and Tang (2003) and subsequently proved to be exact by Jiang and Deng (2012). Sorenson and Webster (2017) determined and . A seven-step test utilizing older bounds on these results (Riesel 1994) allows all numbers less than to be tested.

Zhang (2001, 2002, 2005, 2006, 2007) conjectured that

			(21)
			(22)
			(23)
			(24)
			(25)
			(26)
			(27)

The Baillie-PSW primality test is a test based on a combination of strong pseudoprimes and Lucas pseudoprimes proposed by Pomerance et al. (Pomerance et al. 1980, Pomerance 1984).