STRONG PSEUDOPRIME

In number theory, a 'strong pseudoprime' is a number that passes a strong pseudoprimality test to a given base. All primes pass this test, but a small fraction of composites pass as well, making them "false primes".

Contents

Formal definition

Properties of strong pseudoprimes

Examples

References

Formal definition

Formally, a composite number ''n'' := ''d'' · 2^''s'' + 1 is called a strong pseudoprime to 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)$
It should be noted, however, that Guy uses a definition with only the first condition. 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 to base ''a'' (Pomerance, Selfridge, Wagstaff 1980), but not all Euler pseudoprimes are strong pseudoprimes. Some Fermat pseudoprimes and Carmichael numbers are also strong pseudoprimes.
As Monier and Rabin showed in 1980, a composite number ''n'' is a strong pseudoprime to at most one quarter of all bases <''n''; thus, there are no "strong Carmichael numbers", numbers that are strong pseudoprimes to all bases.
It can, however, be proven that there are infinitely many strong pseudoprimes to any base.

Examples

The first few strong pseudoprimes to base 2 are 2047, 3277, 4033, 4681, 8321, 15841, 29341, ... ; the first few strong pseudoprimes to base 3 are 121, 703, 1891, 3281, 8401, 8911, 10585, ... .

References

★ C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., ''The pseudoprimes to 25 · 10⁹'', Math. Comp., 35:151 (1980) 1003-1026

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