Glossary:
Prime Pages:
Top 5000:
|
One way to make the Fermat probable primality test more
accurate is to write
n-1=2sd where d is
odd and s is
nonnegative. Then n is a strong probable-prime base a (an
a-SPRP) if either ad = 1 (mod n) or
(ad)2r = -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 % |
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) References:
- Bressoud89
- D. M. Bressoud, Factorizations and primality testing, Springer-Verlag, New York, NY, ISBN 0387970401. 1989. MR 91e:11150 [QA161.F3B73]
- Jaeschke93
- G. Jaeschke, "On strong pseudoprimes to several bases," Math. Comp., 61 (1993) 915-926. MR 94d:11004 [Greatly extends the computations of [PSW80] useful for testing small numbers.]
- PSW80
- C. Pomerance, J. L. Selfridge and Wagstaff, Jr., S. S., "The pseudoprimes to 25 · 109," Math. Comp., 35:151 (1980) 1003-1026. MR 82g:10030 [See Richard Pinch's lists of pseudoprimes and [Jaeschke93].]
- Ribenboim95
- P. Ribenboim, The new book of prime number records, 3rd edition, Springer-Verlag, New York, NY, pp. xxiv+541, ISBN 0-387-94457-5. 1995. 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 volume 126, Birkhäuser Boston, Boston, MA, ISBN 0-8176-3743-5. 1994. 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.]
|
