Strong pseudoprime

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 n = 31697 is a probable prime (PRP). We pick base a = 3 and, inspired by Fermat's little theorem, calculate:

$3^{31696}\equiv 1{\pmod {31697}}$

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

$3^{15848}\equiv 1{\pmod {31697}}$

$3^{7924}\equiv 1{\pmod {31697}}$

$3^{3962}\equiv 28419{\pmod {31697}}$

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 not 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:

$3^{47196}\equiv 1{\pmod {47197}}$

$3^{23598}\equiv 1{\pmod {47197}}$

$3^{11799}\equiv 1{\pmod {47197}}$

In this case, the result continues to be +1 (mod 47197) until we reach an odd exponent. In this situation, we say that 47197 is 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:

$3^{74592}\equiv 1{\pmod {74593}}$

$3^{37296}\equiv 1{\pmod {74593}}$

$3^{18648}\equiv 74592\equiv -1{\pmod {74593}}$

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 is a strong probable prime (and, as it turns out, a strong pseudoprime) to base 3.

Formal definition

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

$a^{d}\equiv 1{\pmod {n}}$

or

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.$

(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 a ≡ ±1 (mod n) so these trivial bases are often excluded.

Guy mistakenly gives a definition with only the first condition, which is not satisfied by all primes.

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 25×10⁹, 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, ... (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, ... (sequence A020229 in the OEIS).

The first to base 5 are

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (sequence A020231 in the OEIS).

For base 4, see (sequence A020230 in the OEIS), and for bases 6 to 100, see (sequence A020232 in the OEIS) to (sequence A020326 in the OEIS). 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; 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 $<2^{64}$ 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 a
(sequence A298756 in the OEIS)

a	SPSP		a	SPSP		a	SPSP		a	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 c, 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 overpseudoprime 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 (OEIS: A000265) 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, ... (sequence A141232 in the OEIS)

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, ... (sequence A141350 in the OEIS)

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, ... (sequence A141390 in the OEIS)

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, ... (sequence A400102 in the OEIS)

Least overpseudoprime to base a

Least overpseudoprime to base a

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)		a	OPSP	the number n such that this OPSP divides Zs(n,a,1)
1	9	–		33	545	4		65	33	2		97	49	2
2	2047	11		34	33	1		66	65	1		98	9	2
3	121	5		35	9	2		67	33	1		99	25	2
4	341	5		36	35	1		68	25	4		100	9	1
5	781	5		37	9	1		69	35	2		101	25	1
6	1111	10		38	39	2		70	69	1		102	133	3
7	25	4		39	1561	3		71	9	2		103	51	1
8	9	2		40	39	1		72	85	4		104	15	2
9	91	3		41	21	2		73	9	1		105	451	10
10	9	1		42	529	22		74	15	2		106	15	1
11	133	3		43	21	1		75	91	6		107	9	2
12	133	6		44	9	2		76	15	1		108	91	6
13	85	4		45	481	12		77	39	2		109	9	1
14	15	2		46	9	1		78	77	1		110	111	2
15	14041	18		47	65	4		79	39	1		111	55	1
16	15	1		48	49	2		80	9	2		112	65	4
17	9	2		49	25	2		81	91	3		113	57	2
18	25	4		50	49	1		82	9	1		114	115	2
19	9	1		51	25	1		83	21	2		115	57	1
20	21	2		52	51	1		84	85	2		116	9	2
21	221	4		53	9	2		85	21	1		117	49	6
22	21	1		54	55	2		86	85	1		118	9	1
23	169	6		55	9	1		87	247	3		119	15	2
24	25	2		56	55	1		88	87	1		120	119	1
25	217	3		57	25	4		89	9	2		121	15	1
26	9	2		58	57	1		90	91	2		122	65	4
27	121	5		59	15	2		91	9	1		123	85	4
28	9	1		60	841	28		92	91	1		124	25	2
29	15	2		61	15	1		93	25	4		125	9	2
30	49	3		62	9	2		94	93	1		126	25	1
31	15	1		63	529	22		95	1891	5		127	9	1
32	25	4		64	9	1		96	95	1		128	49	3

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

a	the least overpseudoprime to base a	the least strong pseudoprime to base a
6	1111	217
12	133	91
15	14041	1687
39	1561	133
42	529	451
60	841	481
120	119	91
144	133	91
160	159	91
204	203	91
220	219	91
285	143	91
303	1247	247
322	321	247
330	329	133
345	341	301
402	403	91
417	209	91
470	469	217
477	119	91
495	247	217
510	451	301
517	129	91
534	533	91
590	589	133
591	295	259
670	669	427
675	169	91
690	689	91
750	361	91
790	361	91
816	815	247
825	413	133
831	415	91
840	841	703
867	169	133
870	721	341
873	437	133
903	365	341
939	235	91
945	473	341
954	955	481
963	481	91
972	973	91
1023	511	91