Strong Pseudoprime

A strong pseudoprime to a base is an odd composite number with (for odd) 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. A composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (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.

The strong -pseudoprime test for , 3, 5 correctly identifies all primes below with only 13 exceptions, and if 7 is added, then the only exception less than is 3215031751. 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 number for which the Rabin-Miller strong pseudoprime test on bases less than or equal to the th prime fails). Jaeschke (1993) computed from to 8 and gave upper bounds for to 11.

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

(OEIS A014233), where the bounds for , , and were determined by Zhang and Tang (2003). 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

			(19)
			(20)
			(21)
			(22)
			(23)
			(24)
			(25)
			(26)
			(27)
			(28)
			(29)
			(30)

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).