Strong Pseudoprime

A strong pseudoprime to a base $a$ is an Odd Composite Number $n$ with $n-1=d\cdot 2^s$ (for $d$ Odd) for which either

$$a^d\equiv 1\ \left({{\rm mod\ } {n}}\right)$$ (1)

or

$$a^{d\cdot 2^r}\equiv -1\ \left({{\rm mod\ } {n}}\right)$$ (2)

for some $r\in[0,s)$.

The definition is motivated by the fact that a Fermat Pseudoprime $n$ to the base $b$ satisfies

$$b^{n-1}-1\equiv 0\ \left({{\rm mod\ } {n}}\right).$$ (3)

But since $n$ is Odd, it can be written $n=2m+1$, and

$$b^{2m}-1 =(b^m-1)(b^m+1) \equiv 0 {\rm\ (mod\ } n).$$ (4)

If $n$ is Prime, it must Divide at least one of the Factors, but can't Divide both because it would then Divide their difference

$$(b^m+1)-(b^m-1)=2.$$ (5)

Therefore,

$$b^m\equiv \pm 1\ \left({{\rm mod\ } {n}}\right),$$ (6)

so write $n=2^at+1$ to obtain

$$b^{n-1}-1=(b^t-1)(b^t+1)(b^{2t}+1)\cdots(b^{2^{a-1}t}+1).$$ (7)

If $n$ 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 $a$ is also an Euler Pseudoprime to the base $a$ (Pomerance et al. 1980). The strong pseudoprimes include some Euler Pseudoprimes, Fermat Pseudoprimes, and Carmichael Numbers.

There are 4842 strong psp(2) less than $2.5\times 10^{10}$, where a psp(2) is also known as a Poulet Number. The strong $k$-pseudoprime test for $k=2$, 3, 5 correctly identifies all Primes below $2.5\times 10^{10}$ with only 13 exceptions, and if 7 is added, then the only exception less than $2.5\times 10^{10}$ is 315031751. Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than $10^{12}$, nine if 7 is added, and none if 11 is added. Also, the bases 2, 13, 23, and 1662803 have no exceptions up to $10^{12}$.

If $n$ is Composite, then there is a base for which $n$ is not a strong pseudoprime. There are therefore no ``strong Carmichael Numbers.'' Let $\psi_k$ denote the smallest strong pseudoprime to all of the first $k$ 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 $k$ fails). Jaeschke (1993) computed $\psi_k$ from $k=5$ to 8 and gave upper bounds for $k=9$ to 11.

$$\psi_1 = 2047$$

$$\psi_2 = 1373653$$

$$\psi_3 = 25326001$$

$$\psi_4 = 3215031751$$

$$\psi_5 = 2152302898747$$

$$\psi_6 = 3474749660383$$

$$\psi_7 = 341550071728321$$

$$\psi_8 = 341550071728321$$

$$\psi_9 \leq 41234316135705689041$$

$$\psi_{10} \leq 1553360566073143205541002401$$

$$\psi_{11} \leq 56897193526942024370326972321$$

(Sloane's A014233). A seven-step test utilizing these results (Riesel 1994) allows all numbers less than $3.4\times 10^{14}$ to be tested.

Pomerance et al. (1980) have proposed a test based on a combination of Strong Pseudoprimes and Lucas Pseudoprimes. They offer a $620 reward for discovery of a Composite Number which passes their test (Guy 1994, p. 28).

See also Carmichael Number, Miller's Primality Test, Poulet Number, Rabin-Miller Strong Pseudoprime Test, Rotkiewicz Theorem, Strong Elliptic Pseudoprime, Strong Lucas Pseudoprime

References

Baillie, R. and Wagstaff, S. ``Lucas Pseudoprimes.'' Math. Comput. 35, 1391-1417, 1980.

Guy, R. K. ``Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes.'' §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Jaeschke, G. ``On Strong Pseudoprimes to Several Bases.'' Math. Comput. 61, 915-926, 1993.

Monier, L. ``Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms.'' Theor. Comput. Sci. 12, 97-108, 1980.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. ``The Pseudoprimes to $25\cdot 10^9$.'' Math. Comput. 35, 1003-1026, 1980. Available electronically from ftp://sable.ox.ac.uk/pub/math/primes/ps2.Z.

Rabin, M. O. ``Probabilistic Algorithm for Testing Primality.'' J. Number Th. 12, 128-138, 1980.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, p. 92, 1994.

Sloane, N. J. A. Sequence A014233 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.