Strong pseudoprime

From Wikipedia, the free encyclopedia

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

Contents

[edit] Formal definition

Formally, a composite number n = d · 2s + 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.

[edit] 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].

[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, ... (A020229).

The first to base 5 are

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

[edit] References

  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 · 109. 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.