A strong pseudoprime to a base is an Odd Composite Number with
(for Odd) for
which either
(1) |
(2) |
The definition is motivated by the fact that a Fermat Pseudoprime to the base satisfies
(3) |
(4) |
(5) |
(6) |
(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.
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.
© 1996-9 Eric W. Weisstein