Editing Strong pseudoprime (section)

==Properties of strong pseudoprimes==
A strong pseudoprime to base ''a'' is always an [[Euler–Jacobi pseudoprime]], an [[Euler pseudoprime]]<ref name="PSW">{{cite journal|author1=Carl Pomerance|author-link1=Carl Pomerance|author2=John L. Selfridge|author-link2=John L. Selfridge|author3=Samuel S. Wagstaff Jr.|author-link3=Samuel S. Wagstaff Jr.|title=The pseudoprimes to 25·10<sup>9</sup>|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 |doi-access=free}}</ref> and a [[Fermat pseudoprime]] to that base, but not all Euler and Fermat pseudoprimes are strong pseudoprimes. [[Carmichael number]]s 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'';<ref>
{{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|author-link=Louis Monier
 |doi-access=free}}
</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]]. The true probability of a failure is generally vastly smaller. [[Paul Erdős]] and [[Carl Pomerance]] showed in 1986 that if a random integer n passes the Miller–Rabin primality test to a random base b, then n is [[almost all|almost surely]] a prime.<ref>{{cite web|url=https://primes.utm.edu/notes/prp_prob.html|title=Probable primes: How probable?|access-date=October 23, 2020}}</ref> For example, of the first 25,000,000,000 positive integers, there are 1,091,987,405 integers that are probable primes to base 2, but only 21,853 of them are pseudoprimes, and even fewer of them are strong pseudoprimes, as the latter is a subset of the former.<ref>{{cite web|url=https://primes.utm.edu/glossary/page.php?sort=PRP|title=The Prime Glossary: probable prime}}</ref>
However, Arnault
<ref name="Arnault397Digit">{{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|doi=10.1006/jsco.1995.1042|doi-access=free}}</ref>
gives a 397-digit Carmichael number that is a strong pseudoprime to every base less than 307.
One way to reduce the chance that such a number is wrongfully declared probably prime is to combine a strong probable prime test with a [[Lucas pseudoprime|Lucas probable prime]] test, as in the [[Baillie–PSW primality test]].

There are infinitely many strong pseudoprimes to any base.<ref name="PSW"/>