## Strong Pseudoprime

A strong pseudoprime to a base is an Odd Composite Number with (for Odd) for which either

 (1)

or
 (2)

for some .

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.

There are 4842 strong psp(2) less than , where a psp(2) is also known as a Poulet Number. 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 315031751. 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 fails). Jaeschke (1993) computed from to 8 and gave upper bounds for to 11.

(Sloane's A014233). A seven-step test utilizing these results (Riesel 1994) allows all numbers less than 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 .'' 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.