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".

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^{d}\equiv 1\mod n

a^{d\cdot 2^{r}}\equiv -1\mod n\quad {\mbox{ for some }}0\leq r\leq (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 ^[1]. 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 ^[2] and a Fermat pseudoprime ^{[citation needed]} 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 ^[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 ^{[citation needed]}.

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 the 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, ... (OEIS: A020229).

The first to base 5 are

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (OEIS: A020231).

References

^ Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
^ Pomerance, Selfridge and Wagstaff, The pseudoprimes to 25 · 10⁹. 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.

[1] Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

[2] Pomerance, Selfridge and Wagstaff, The pseudoprimes to 25 · 10⁹. Mathematics of Computation, 35:151 pp. 1003-1026, 1980.

[3] Monier, Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms. Theoretical Computer Science, 12 pp. 97-108, 1980.

[4] Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.

[1]

[2]

[3]

[4]