strong probable prime

One way to make the Fermat probable primality test more accurate is to write n-1=2^sd where d is odd and s is nonnegative. Then n is a strong probable-prime base a (an a-SPRP) if either a^d = 1 (mod n) or (a^d)^{2^r} = -1 (mod n) for some nonnegative r less than s.

All integers n greater than one which fail this test are composite; integers that pass it might be prime. The smallest odd composite SPRPs are the following.

base all composite SPRPs less than 20,000 percentage

2 2047, 3277, 4033, 4681, 8321, 15841 0.07 %

3 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345 0.14 %

5 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751 0.10 %

7 25, 325, 703, 2101, 2353, 4525, 11041, 14089 0.10 %

11 133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711 0.11 %

13 85, 1099, 5149, 7107, 8911, 9637, 13019, 14491, 17803, 19757 0.12 %

17 9, 91, 145, 781, 1111, 2821, 4033, 4187, 5365, 5833, 6697, 7171, 15805, 19729 0.18 %

19 9, 49, 169, 343, 1849, 2353, 2701, 4033, 4681, 6541, 6697, 7957, 9997, 12403, 13213, 13747, 15251, 16531, 18769, 19729 0.25 %

23 169, 265, 553, 1271, 2701, 4033, 4371, 4681, 6533, 6541, 7957, 8321, 8651, 8911, 9805, 14981, 18721 0.21 %

29 15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 6097, 8401, 11581, 12431, 15577, 16471, 19093 0.20 %

31 15, 49, 133, 481, 931, 6241, 8911, 9131, 10963, 11041, 14191, 17767 0.15 %

37 9, 451, 469, 589, 685, 817, 1333, 3781, 8905, 9271, 18631, 19517 0.15 %

41 21, 231, 671, 703, 841, 1281, 1387, 1417, 2701, 3829, 8321, 8911, 10933, 13019, 14091 0.19 %

43 21, 25, 185, 925, 1541, 1807, 3281, 3439, 3781, 4417, 7081, 8857, 10609, 11989, 14089, 18721 0.20 %

47 65, 85, 221, 341, 703, 721, 1105, 1891, 2257, 2465, 5461, 9361, 9881, 15769, 19669 0.19 %

53 9, 27, 91, 1405, 1441, 1541, 2209, 2863, 3367, 3481, 5317, 6031, 9409, 11359, 14833, 17141, 17461 0.21 %

59 15, 451, 1141, 1247, 1541, 1661, 1991, 2413, 3097, 4681, 5611, 6191, 7421, 8149, 9637, 10081, 10217, 12083, 13981 0.24 %

61 15, 217, 341, 1261, 2701, 3661, 6541, 6697, 7613, 13213, 16213 0.14 %

67 33, 49, 217, 703, 1519, 2209, 2245, 6119, 8371, 11521, 12403, 14981, 18721 0.16 %

71 9, 35, 1387, 1921, 2071, 2209, 2321, 6541, 7957, 8365, 8695, 9809, 10349, 11041, 13747, 16589 0.20 %

73 9, 65, 205, 259, 533, 1441, 1921, 2665, 3439, 5257, 15457 0.14 %

79 39, 49, 91, 301, 559, 637, 1649, 2107, 2701, 3913, 6533, 7051, 8321, 9881, 12001, 14491, 14981, 16721, 17753, 19951 0.25 %

83 21, 65, 231, 265, 689, 703, 1241, 3445, 4411, 6973, 8421, 12871, 15883, 18721 0.18 %

89 9, 15, 45, 169, 1035, 1441, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711, 11521, 12403 0.21 %

97 49, 341, 469, 481, 949, 973, 2701, 3283, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313, 10585, 14981, 18487 0.24 %

101 25, 51, 91, 259, 481, 561, 2431, 3367, 6649, 6697, 7701, 9073, 12403, 13333, 15221, 16471, 19951 0.21 %

base	all composite SPRPs less than 20,000	percentage
2	2047, 3277, 4033, 4681, 8321, 15841	0.07 %
3	121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345	0.14 %
5	781, 1541, 5461, 5611, 7813, 13021, 14981, 15751	0.10 %
7	25, 325, 703, 2101, 2353, 4525, 11041, 14089	0.10 %
11	133, 793, 2047, 4577, 5041, 12403, 13333, 14521, 17711	0.11 %
13	85, 1099, 5149, 7107, 8911, 9637, 13019, 14491, 17803, 19757	0.12 %
17	9, 91, 145, 781, 1111, 2821, 4033, 4187, 5365, 5833, 6697, 7171, 15805, 19729	0.18 %
19	9, 49, 169, 343, 1849, 2353, 2701, 4033, 4681, 6541, 6697, 7957, 9997, 12403, 13213, 13747, 15251, 16531, 18769, 19729	0.25 %
23	169, 265, 553, 1271, 2701, 4033, 4371, 4681, 6533, 6541, 7957, 8321, 8651, 8911, 9805, 14981, 18721	0.21 %
29	15, 91, 341, 469, 871, 2257, 4371, 4411, 5149, 6097, 8401, 11581, 12431, 15577, 16471, 19093	0.20 %
31	15, 49, 133, 481, 931, 6241, 8911, 9131, 10963, 11041, 14191, 17767	0.15 %
37	9, 451, 469, 589, 685, 817, 1333, 3781, 8905, 9271, 18631, 19517	0.15 %
41	21, 231, 671, 703, 841, 1281, 1387, 1417, 2701, 3829, 8321, 8911, 10933, 13019, 14091	0.19 %
43	21, 25, 185, 925, 1541, 1807, 3281, 3439, 3781, 4417, 7081, 8857, 10609, 11989, 14089, 18721	0.20 %
47	65, 85, 221, 341, 703, 721, 1105, 1891, 2257, 2465, 5461, 9361, 9881, 15769, 19669	0.19 %
53	9, 27, 91, 1405, 1441, 1541, 2209, 2863, 3367, 3481, 5317, 6031, 9409, 11359, 14833, 17141, 17461	0.21 %
59	15, 451, 1141, 1247, 1541, 1661, 1991, 2413, 3097, 4681, 5611, 6191, 7421, 8149, 9637, 10081, 10217, 12083, 13981	0.24 %
61	15, 217, 341, 1261, 2701, 3661, 6541, 6697, 7613, 13213, 16213	0.14 %
67	33, 49, 217, 703, 1519, 2209, 2245, 6119, 8371, 11521, 12403, 14981, 18721	0.16 %
71	9, 35, 1387, 1921, 2071, 2209, 2321, 6541, 7957, 8365, 8695, 9809, 10349, 11041, 13747, 16589	0.20 %
73	9, 65, 205, 259, 533, 1441, 1921, 2665, 3439, 5257, 15457	0.14 %
79	39, 49, 91, 301, 559, 637, 1649, 2107, 2701, 3913, 6533, 7051, 8321, 9881, 12001, 14491, 14981, 16721, 17753, 19951	0.25 %
83	21, 65, 231, 265, 689, 703, 1241, 3445, 4411, 6973, 8421, 12871, 15883, 18721	0.18 %
89	9, 15, 45, 169, 1035, 1441, 2611, 2977, 3961, 4187, 5461, 6697, 7107, 7601, 7711, 11521, 12403	0.21 %
97	49, 341, 469, 481, 949, 973, 2701, 3283, 4187, 4371, 4705, 6811, 8023, 8119, 8911, 9313, 10585, 14981, 18487	0.24 %
101	25, 51, 91, 259, 481, 561, 2431, 3367, 6649, 6697, 7701, 9073, 12403, 13333, 15221, 16471, 19951	0.21 %

A test based on these results is quite fast, especially when combined with trial division by the first few primes. If you have trouble programming these results, Riesel [Riesel94] has PASCAL code for a SPRP test and Bressoud [Bressoud89] has pseudocode.

Individually these tests are still weak (there are infinitely many a-SPRP's for every base a > 1), but we can combine these individual tests to make powerful tests for small integers n:

If n < 1,373,653 is both a 2 and 3-SPRP, then n is prime.
If n < 25,326,001 is a 2, 3, and 5-SPRP, then n is prime.
If n < 118,670,087,467 is a 2, 3, 5, and 7-SPRP, then either n = 3,215,031,751 or n is prime.
If n < 2,152,302,898,747 is a 2, 3, 5, 7, and 11-SPRP, then n is prime.
If n < 3,474,749,660,383 is a 2, 3, 5, 7, 11, and 13-SPRP, then n is prime.
If n < 341,550,071,728,321 is a 2, 3, 5, 7, 11, 13, and 17-SPRP, then n is prime.

If we do not require that the bases be consecutive primes, we have:

If n < 9,080,191 is both a 31 and 73-SPRP, then n is prime.
If n < 4,759,123,141 is a 2, 7, and 61-SPRP, then n is prime.
If n < 1,000,000,000,000 is a 2, 13, 23, and 1662803-SPRP, then n is prime.

See Also: PRP, Pseudoprime, FrobeniusPseudoprime, MillersTest

Related pages (outside of this work)

Fermat, Probable-Primality and Pseudoprimes

References:

Bressoud89
D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, 1989. New York, NY, ISBN 0387970401. MR 91e:11150 [QA161.F3B73]
Jaeschke93
G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926. MR 94d:11004
PSW80
C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 10⁹," Math. Comp., 35:151 (1980) 1003-1026. MR 82g:10030
Ribenboim95
P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, 1995. pp. xxiv+541, ISBN 0-387-94457-5. MR 96k:11112 [An excellent resource for those with some college mathematics. Basically a Guinness Book of World Records for primes with much of the relevant mathematics. The extensive bibliography is seventy-five pages.]
Riesel94
H. Riesel, Prime numbers and computer methods for factorization, Progress in Mathematics Vol, 126, Birkhäuser Boston, Boston, MA, 1994. ISBN 0-8176-3743-5. MR 95h:11142 [An excellent reference for those who want to start to program some of these algorithms. Code is provided in Pascal. Previous edition was vol. 57, 1985.]