Euler probable prime
Fermat's little theorem tells us that if the integer a is not divisible by the prime p, then ap-1 is one modulo p. Euler was able to prove the stronger statement: a(p-1)/2 = (a|p) (mod p) where (a|p) is the Jacobi symbol. So we can use this as a test for probable primality: given relatively prime integers a and n, we say n is an Euler probable prime (base a)(an Euler PRP) if
a(n-1)/2 = (a|n) (mod n).
If this is the case and n is composite, then we say n is an Euler pseudoprime (base a).
There are 101,629 pseudoprimes base two less than 1,000,000,000,000 and roughly half: 53,332 are Euler pseudoprimes (22,407 of these are strong pseudoprimes). Since the Jacobi symbol is very easy to calculate, this gives us a test for primality that is roughly twice a s strong as a weak Fermat test, but a very little extra cost.
Below is a table of the odd composite Euler PRP's less than 3000 and the percentage of the odd composites in this range that are not exposed as composite by this test.
| base | composite odd Euler PRP's < 3000 | percentage |
|---|---|---|
| 2 | 561, 1105, 1729, 1905, 2047, 2465 | 0.6% |
| 3 | 121, 1729, 2821 | 0.3% |
| 5 | 781, 1541, 1729 | 0.3% |
| 7 | 25, 703, 2101,2353, 2465 | 0.5% |
| 11 | 133, 793, 2465 | 0.3% |
| 13 | 105, 1785 | 0.2% |
| 17 | 9, 145, 781, 1305, 2821 | 0.5% |
| 19 | 9, 45, 49, 169, 1849, 2353 | 0.6% |
| 23 | 169, 265, 553, 1729, 2465 | 0.5% |
| 29 | 91, 341, 469, 871, 2257 | 0.5% |
| 31 | 15, 49, 133, 481, 2465 | 0.5% |
| 37 | 9, 451, 469, 589, 817, 1233, 1333, 1729 | 0.7% |
| 41 | 21, 105, 841, 1065, 1281, 1417, 2465, 2701 | 0.7% |
| 43 | 21, 25, 185, 385, 1541, 1729, 2465, 2553, 2849 | 0.8% |
| 47 | 65, 341, 345, 703, 721, 897, 1105, 1649, 1729, 1891, 2257, 2465 | 1.1% |
| 53 | 9, 91, 117, 1441, 1541, 2209, 2529, 2863 | 0.7% |
| 59 | 145, 451, 1141, 1247, 1541, 1661, 1991, 2413, 2465 | 0.8% |
| 61 | 15, 217, 341, 1261, 2465, 2821 | 0.6% |
| 67 | 33, 49, 217, 561, 1105, 1309, 1519, 1729, 2209 | 0.8% |
See Also: StrongPRP, CarmichaelNumber, Pseudoprime, FrobeniusPseudoprime
References:
- 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
- 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.]