Strong pseudoprime

In number theory, a strong pseudoprime is a composite number that passes a pseudoprimality test. All primes pass this test, but a small fraction of composites pass as well, making them "false primes". Unlike the Fermat pseudoprimes, for which there exist numbers that are pseudoprimes to all bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.

Formal definition

Formally, a composite number "n" = "d" · 2^"s" + 1 is called a strong pseudoprime to a relatively prime base "a" iff one of the following conditions hold:

: $a^dequiv\; 1mod\; n$

: $a^\{dcdot\; 2^r\}equiv\; -1mod\; nquadmbox\{\; for\; some\; \}0leq\; rleq(s-1)$

The definition of a strong pseudoprime depends on the base used; different bases have different strong pseudoprimes.

It should be noted, however, that Guy uses a definition with only the first condition [Guy, "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in "Unsolved Problems in Number Theory", 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.] . Because not all primes pass that condition, this definition of 'strong pseudoprimes' resembles the primes less closely.

Properties of strong pseudoprimes

A strong pseudoprime to base "a" is always an Euler pseudoprime Pomerance, Selfridge and Wagstaff, "The pseudoprimes to 25 · 10⁹." "Mathematics of Computation", 35:151 pp. 1003-1026, 1980.] and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Some Carmichael numbers are also strong pseudoprimes.

A composite number "n" is a strong pseudoprime to at most one quarter of all bases below "n" [Monier, "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms." "Theoretical Computer Science", 12 pp. 97-108, 1980.] [Rabin, "Probabilistic Algorithm for Testing Primality." "Journal of Number Theory", 12 pp. 128-138, 1980.] ; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases. Thus given a random base, the probability that a number is a strong pseudoprime to that base is less than 1/4, forming the basis of the widely-used Miller-Rabin primality test. However, there are still infinitely many strong pseudoprimes to any base.

Examples

The first strong pseudoprimes to base 2 are:2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... OEIS|id=A001262.The first to base 3 are:121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (OEIS2C|id=A020229).The first to base 5 are:781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (OEIS2C|id=A020231).

References