Strong pseudoprime: Difference between revisions

Content deleted Content added

Inline

Revision as of 20:56, 27 August 2008

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^{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 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^[2].

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.
^ ^a ^b 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.

[PSW-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]

@@ Line 1: / Line 1: @@
-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 "[[pseudoprime|false primes]]".(a composite number may pass the test for a few bases but if checked with all the bases it won't pass it, which means there are no semi 'Carmichael' numbers for this test)
+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 "[[pseudoprime|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 ==
@@ Line 15: / Line 15: @@
 == Properties of strong pseudoprimes ==
-A strong pseudoprime to base ''a'' is always an [[Euler pseudoprime]] <ref>[[Carl Pomerance|Pomerance]], [[John Selfridge|Selfridge]] and [[Samuel S. Wagstaff Jr.|Wagstaff]], ''The pseudoprimes to 25 · 10<sup>9</sup>.'' ''Mathematics of Computation'', 35:151 pp. 1003-1026, 1980.</ref> and a [[Fermat pseudoprime]] {{Fact|date=April 2008}} to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Some [[Carmichael number]]s are also strong pseudoprimes.
+A strong pseudoprime to base ''a'' is always an [[Euler pseudoprime]] <ref name="PSW">[[Carl Pomerance|Pomerance]], [[John Selfridge|Selfridge]] and [[Samuel S. Wagstaff Jr.|Wagstaff]], ''The pseudoprimes to 25 · 10<sup>9</sup>.'' ''Mathematics of Computation'', 35:151 pp. 1003-1026, 1980.</ref> and a [[Fermat pseudoprime]] to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. Some [[Carmichael number]]s are also strong pseudoprimes.
-A composite number ''n'' is a strong pseudoprime to at most one quarter of all bases below ''n'' <ref>[[Louis Monier|Monier]], ''Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms.'' ''Theoretical Computer Science'', 12 pp. 97-108, 1980.</ref><ref>[[Michael O. Rabin|Rabin]], ''Probabilistic Algorithm for Testing Primality.'' ''Journal of Number Theory'', 12 pp. 128-138, 1980.</ref>; 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 {{Fact|date=April 2008}}.
+A composite number ''n'' is a strong pseudoprime to at most one quarter of all bases below ''n'' <ref>[[Louis Monier|Monier]], ''Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms.'' ''Theoretical Computer Science'', 12 pp. 97-108, 1980.</ref><ref>[[Michael O. Rabin|Rabin]], ''Probabilistic Algorithm for Testing Primality.'' ''Journal of Number Theory'', 12 pp. 128-138, 1980.</ref>; 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<ref name="PSW"/>.
 == Examples ==