“Strong pseudoprime”的意思、由来-开放百科全书

A strong probable prime is a number that passes a strong version of a primality test.

A strong pseudoprime is a composite number that passes a strong version of a primality test.

All primes pass these tests, but a small fraction of composites also pass, 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.

Formal definition

An odd composite number n = d · 2^s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a when one of the following conditions holds:

(If a number n satisfies one of the above conditions and we don't yet know whether it is prime, it is more precise to refer to it as a strong probable prime to base a. But if we know that n is not prime, then one may use the term strong pseudoprime.)

The definition is trivially met if {{math|a ≡ ±1 (mod n)}} so these trivial bases are often excluded.

Properties of strong pseudoprimes

A strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, 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.

gives a 397-digit Carmichael number that is a strong pseudoprime to every base less than 307.

One way to prevent such a number from wrongfully being declared probably prime is to combine a strong probable prime test with a Lucas probable prime test, as in the Baillie–PSW primality test.

Examples

For base 4, see {{oeis|id=A020230}}, and for base 6 to 100, see {{oeis|id=A020232}} to {{oeis|id=A020326}}.

By testing the above conditions to several bases, one gets somewhat more powerful primality tests than by using one base alone.

For example, there are only 13 numbers less than 25·10⁹ that are strong pseudoprimes to bases 2, 3, and 5 simultaneously.

This means that, if n is less than 25326001 and n is a strong probable prime to bases 2, 3, and 5, then n is prime.

Carrying this further, 3825123056546413051 is the smallest number that is a strong pseudoprime to the 9 bases 2, 3, 5, 7, 11, 13, 17, 19, and 23.^[6]

So, if n is less than 3825123056546413051 and n is a strong probable prime to these 9 bases, then n is prime.

By judicious choice of bases that are not necessarily prime, even better tests can be constructed. For example, there is no composite

that is a strong pseudoprime to all of the seven bases 2, 325, 9375, 28178, 450775, 9780504, and 1795265022.^[8]

Smallest strong pseudoprime to base n

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. ^¹²{{cite journal|author1=Carl Pomerance|authorlink1=Carl Pomerance|author2=John L. Selfridge|authorlink2=John L. Selfridge|author3=Samuel S. Wagstaff, Jr.|authorlink3=Samuel S. Wagstaff, Jr.|title=The pseudoprimes to 25·10⁹|journal=Mathematics of Computation|date=July 1980|volume=35|issue=151|pages=1003–1026|url=http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf| doi=10.1090/S0025-5718-1980-0572872-7 }}
3. ^{{cite journal |title=Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms |author=Louis Monier |journal=Theoretical Computer Science |date=1980 |volume=12 |pages=97–108 |doi=10.1016/0304-3975(80)90007-9}}
4. ^Rabin, Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 12 pp. 128-138, 1980.
5. ^{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases|journal=Journal of Symbolic Computation|date=August 1995|volume=20|issue=2|pages=151–161|author=F. Arnault|url=http://www.sciencedirect.com/science/article/pii/S0747717185710425|doi=10.1006/jsco.1995.1042}}
6. ^{{cite journal|title=Finding Strong Pseudoprimes to Several Bases. II|journal=Mathematics of Computation|year=2003|volume=72|issue=244|pages=2085–2097|author1=Zhenxiang Zhang|author2=Min Tang|doi=10.1090/S0025-5718-03-01545-X }}
7. ^{{cite arXiv |last1=Jiang |first1=Yupeng |last2=Deng |first2=Yingpu |eprint=1207.0063v1|title=Strong pseudoprimes to the first 9 prime bases |class=math.NT |year=2012 |version= }}
8. ^{{cite web | url=https://miller-rabin.appspot.com | title=SPRP Records | access-date=3 June 2015}}