Strong pseudoprime
In number theory, a strong pseudoprime is a composite number that passes a primality 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 coprime bases (the Carmichael numbers), there are no composites that are strong pseudoprimes to all bases.
Contents |
[edit] Formal definition
Formally, a composite number n = d · 2s + 1 with d being odd is called a strong pseudoprime to a relatively prime base a when one of the following conditions hold:
The definition of a strong pseudoprime depends on the base used; different bases have different strong pseudoprimes. The definition is trivially met if a ≡ ±1 mod n so these base choices are often excluded.
Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.[1]
[edit] Properties of strong pseudoprimes
A strong pseudoprime to base a is always an Euler pseudoprime [2] and a Fermat pseudoprime to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Carmichael numbers may be strong pseudoprimes to some bases—for example, 561 is a strong pseudoprime to base 50—but not to all bases.
A composite number n is a strong pseudoprime to at most one quarter of all bases below n [3][4]; 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[2].
[edit] 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, ... (sequence A001262 in OEIS).
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, ... (sequence A020229 in OEIS).
The first to base 5 are
- 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (sequence A020231 in OEIS).
[edit] References
- ^ Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
- ^ a b Pomerance, Selfridge and Wagstaff, The pseudoprimes to 25 · 109. Mathematics of Computation, 35:151 pp. 1003-1026, 1980.
- ^ 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.
