A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

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.

Motivation and first examples Let us say we want to investigate if is a probable prime (PRP). We pick base and, inspired by Fermat's little theorem, calculate:

This shows 31697 is a Fermat PRP (base 3), so we may suspect it is a prime. We now repeatedly halve the exponent:

The first couple of times do not yield anything interesting (the result was still 1 modulo 31697), but at exponent 3962 we see a result that is neither 1 nor −1 (i.e. 31696) modulo 31697, proving 31697 is composite, and therefore a strong pseudoprime to base 3. Modulo a prime, the residue 1 can have no other square roots than +1 and −1, but if the modulus is composite, 1 can have square root +1 modulo some factors and −1 modulo others, leading to additional possibilities.

In cases like this, where a number is a Fermat pseudoprime but not a strong pseudoprime, this even gives us a factorization: 31697 = gcd(28419+1, 31697) × gcd(28419−1, 31697) = 29 × 1093.

For another example, pick n = 47197 and calculate in the same manner:

In this case, the result continues to be +1 (mod 47197) until we reach an odd exponent. In this situation, we say that 47197 a strong probable prime to base 3. Because it turns out this PRP is in fact composite (can be seen by picking other bases than 3), we have that 47197 is a strong pseudoprime to base 3.

Finally, consider n = 74593 where we get:

Here, we reach minus −1 modulo 74593, a situation that is perfectly possible with a prime. When this occurs, we stop the calculation (even though the exponent is not odd yet) and say that 74593 a strong probable prime (and, as it turns out, a strong pseudoprime) to base 3.

Formal definition An odd composite number n = d · 2s + 1 where d is odd is called a strong (Fermat) pseudoprime to base a if:

or

(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 we may use the term strong pseudoprime.)

The definition is trivially met if so these trivial bases are often excluded.

Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.Guy, Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Properties of strong pseudoprimes A strong pseudoprime to base a is always an Euler–Jacobi pseudoprime, an Euler pseudoprime 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; 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 surely a prime. For example, of the first odd natural numbers less than , there are 1,091,987,405 probable primes to base 2, but only 21,853 of them are pseudoprimes, and only 4,842 of those are strong pseudoprimes.

However, there are infinitely many strong pseudoprimes to any base, and there exist numbers which are strong pseudoprimes any desired set of bases. Arnault gives a 397-digit Carmichael number that is a strong pseudoprime to every prime 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 probable prime test, as in the Baillie–PSW primality test.

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, ... . 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, ... . The first to base 5 are 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... .

For base 4, see , and for bases 6 to 100, see to . 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·109 that are strong pseudoprimes to bases 2, 3, and 5 simultaneously; the smallest such number is 25326001. 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. 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.

Least strong pseudoprime to base a

+ Least strong pseudoprime to base aa SPSPa SPSPa SPSPa SPSP 1 9 33 545 65 33 97 49 2 2047 34 33 66 65 98 9 3 121 35 9 67 33 99 25 4 341 36 35 68 25 100 9 5 781 37 9 69 35 101 25 6 217 38 39 70 69 102 133 7 25 39 133 71 9 103 51 8 9 40 39 72 85 104 15 9 91 41 21 73 9 105 451 10 9 42 451 74 15 106 15 11 133 43 21 75 91 107 9 12 91 44 9 76 15 108 91 13 85 45 481 77 39 109 9 14 15 46 9 78 77 110 111 15 1687 47 65 79 39 111 55 16 15 48 49 80 9 112 65 17 9 49 25 81 91 113 57 18 25 50 49 82 9 114 115 19 9 51 25 83 21 115 57 20 21 52 51 84 85 116 9 21 221 53 9 85 21 117 49 22 21 54 55 86 85 118 9 23 169 55 9 87 247 119 15 24 25 56 55 88 87 120 91 25 217 57 25 89 9 121 15 26 9 58 57 90 91 122 65 27 121 59 15 91 9 123 85 28 9 60 481 92 91 124 25 29 15 61 15 93 25 125 9 30 49 62 9 94 93 126 25 31 15 63 529 95 1891 127 9 32 25 64 9 96 95 128 49 9, being the least odd composite number, is the least number which can be a pseudoprime, and shows up often because it is a strong pseudoprime to any base a ≡ ±1 (mod 9).

Overpseudoprime

A composite c is called an overpseudoprime base b when the multiplicative order of b mod c × the number of cyclotomic coset (the coset {0} is not counted, e.g. for 2 mod 9 there are 2 cosets: {1, 2, 4, 8, 7, 5}, {3, 6}; for 2 mod 15 there are 4 cosets: {1, 2, 4, 8}, {3, 6, 12, 9}, {5, 10}, {7, 14, 13, 11}; and for 2 mod 21 there are 5 cosets: {1, 2, 4, 8, 16, 11}, {3, 6, 12}, {5, 10, 20, 19, 17, 13}, {7, 14}, {9, 18, 15}) of b mod c equals cVladimir Shevelev, G. Garcia-Pulgarin, J. M. Velasquez and J. H. Castillo, Overpseudoprimes, and Mersenne and Fermat Numbers as Primover Numbers Vladimir Shevelev, Overpseudoprimes, Mersenne Numbers and Wieferich primesJ. H. Castillo, G. García-Pulgarín and J. M. Velásquez-Soto, q-pseudoprimality: A natural generalization of strong pseudoprimality, in fact, the overpseudoprimes base b are exactly the composite factors of the Zsigmondy numbers Zs(n,b,1) for some n. Overpseudoprimes must be strong pseudoprimes, Euler-Jacobi pseudoprimes, Euler pseudoprimes, and Fermat pseudoprimes to the same base b. There are infinitely many overpseudoprimes to every base b.

Every prime p divides only finitely many (including zero) overpseudoprimes in base b, since for all bases b ≥ 2 and all n ≥ 1, there are only finitely many (prime or composite) numbers r such that the multiplicative order of b mod r is n (all of these r are divisors of Zs(n,b,1), of course there are only finitely many divisors of Zs(n,b,1)), and for base b ≥ 2 and prime p, p divides an overpseudoprime in base b if and only if p does not divide b and p is odd and p is not equal to the odd part () of Zs(n,b,1) for any n.

The overpseudoprimes base 2 are

2047, 3277, 4033, 8321, 65281, 80581, 85489, 88357, 104653, 130561, 220729, 253241, 256999, 280601, 390937, 458989, 486737, 514447, 580337, 818201, 838861, 877099, 916327, 976873, ...

The overpseudoprimes base 3 are

121, 703, 3281, 8401, 12403, 31621, 44287, 47197, 55969, 74593, 79003, 88573, 97567, 105163, 112141, 211411, 221761, 226801, 228073, 293401, 313447, 320167, 328021, 340033, 359341, 432821, 443713, 453259, 478297, 497503, ...

The overpseudoprimes base 5 are

781, 1541, 5461, 13021, 15751, 25351, 29539, 38081, 40501, 79381, 100651, 121463, 133141, 195313, 216457, 315121, 318551, 319507, 326929, 341531, 353827, 375601, 416641, 432821, 453331, 464881, 498451, ...

The overpseudoprimes base 10 are

9, 91, 4187, 6533, 8149, 10001, 11111, 50851, 79003, 83119, 94139, 102173, 118957, 148417, 158497, 166499, 201917, 226273, 237169, 287809, 341503, 351809, 413339, 455971, 463241, 481601, 491063, 497377, ...

Least overpseudoprime to base a

+ Least overpseudoprime to base aa OPSP the number n such that this OPSP divides Zs(n,a,1)a OPSP the number n such that this OPSP divides Zs(n,a,1)a OPSP the number n such that this OPSP divides Zs(n,a,1)a OPSP the number n such that this OPSP divides Zs(n,a,1)19–Zsigmondy number Zs(n,a,1) is not defined for a = 13354546533297492220471134331666519892312153592673319925243415363516825410091578153791693521012516111110383927069110213337254391561371921035118924039172854104152991341212739110545110109142529227415210615111133343211759161079212133644927615110891613854454811277392109911415246917877111011121514041184765479391111551161514849280921126541792492528191311357218254504918291114115219915125183212115571202125251184852116922122145392852111174962221154552868511189123169655918724731191522425256551888711201191252173572548992121151269258571909121226542712155915291911238542891608412892911124252291526115193254125923049362929493112625131151635292295189151279132254649196951128493

The least overpseudoprime to base a equals the least strong pseudoprime to base a for most a, for a ≤ 1024, the exceptions are:

athe least overpseudoprime to base athe least strong pseudoprime to base a611112171213391151404116873915611334252945160841481120119911441339116015991204203912202199128514391303124724732232124733032913334534130140240391417209914704692174771199149524721751045130151712991534533915905891335912952596706694276751699169068991750361917903619181681524782541313383141591840841703867169133870721341873437133903365341939235919454733419549554819634819197297391102351191

Notes

References