Euler pseudoprime
Euler pseudoprime
Jump to navigation
Jump to search
In arithmetic, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and
- a(n−1)/2≡±1(modn){displaystyle a^{(n-1)/2}equiv pm 1{pmod {n}}}
(where mod refers to the modulo operation).
The motivation for this definition is the fact that all prime numbers p satisfy the above equation which can be deduced from Fermat's little theorem. Fermat's theorem asserts that if p is prime, and coprime to a, then ap−1 ≡ 1 (mod p). Suppose that p>2 is prime, then p can be expressed as 2q + 1 where q is an integer. Thus, a(2q+1) − 1 ≡ 1 (mod p), which means that a2q − 1 ≡ 0 (mod p). This can be factored as (aq − 1)(aq + 1) ≡ 0 (mod p), which is equivalent to a(p−1)/2 ≡ ±1 (mod p).
The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are twice as strong as tests based on Fermat's little theorem.
Every Euler pseudoprime is also a Fermat pseudoprime. It is not possible to produce a definite test of primality based on whether a number is an Euler pseudoprime because there exist absolute Euler pseudoprimes, numbers which are Euler pseudoprimes to every base relatively prime to themselves. The absolute Euler pseudoprimes are a subset of the absolute Fermat pseudoprimes, or Carmichael numbers, and the smallest absolute Euler pseudoprime is 1729 = 7×13×19.
Contents
1 Relation to Euler-Jacobi pseudoprimes
2 Examples
3 Least Euler pseudoprime to base n
4 See also
5 References
Relation to Euler-Jacobi pseudoprimes[edit]
The slightly stronger condition that
- a(n−1)/2≡(an)(modn){displaystyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}}
where n is an odd composite, the greatest common divisor of a and n equals 1, and (a/n) is the Jacobi symbol, is the more common definition of an Euler pseudoprime.
See, for example, page 115 of the book by Koblitz listed below, page 90 of the book by Riesel, or page 1003 of.[1]
A discussion of numbers of this form can be found at Euler–Jacobi pseudoprime. There are no absolute Euler-Jacobi pseudoprimes.[1]:p. 1004
Examples[edit]
n | Euler pseudoprimes to base n |
1 | 9, 15, 21, 25, 27, 33, 35, 39, 45, 49, 51, 55, 57, 63, 65, 69, 75, 77, 81, 85, 87, 91, 93, 95, 99, 105, 111, 115, 117, 119, 121, 123, 125, 129, 133, 135, 141, 143, 145, 147, 153, 155, 159, 161, 165, 169, 171, 175, 177, 183, 185, 187, 189, 195, 201, 203, 205, 207, 209, 213, 215, 217, 219, 221, 225, 231, 235, 237, 243, 245, 247, 249, 253, 255, 259, 261, 265, 267, 273, 275, 279, 285, 287, 289, 291, 295, 297, 299, ... (all odd composites) |
2 | 341, 561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 5461, 6601, 8321, 8481, ... |
3 | 121, 703, 1541, 1729, 1891, 2465, 2821, 3281, 4961, 7381, 8401, 8911, ... |
4 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... |
5 | 217, 781, 1541, 1729, 5461, 5611, 6601, 7449, 7813, ... |
6 | 185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, ... |
7 | 25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, ... |
8 | 9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, ... |
9 | 91, 121, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... |
10 | 9, 33, 91, 481, 657, 1233, 1729, 2821, 2981, 4187, 5461, 6533, 6541, 6601, 7777, 8149, 8401, ... |
11 | 133, 305, 481, 645, 793, 1729, 2047, 2257, 2465, 4577, 4921, 5041, 5185, 8113, ... |
12 | 65, 91, 133, 145, 247, 377, 385, 1649, 1729, 2041, 2233, 2465, 2821, 3553, 6305, 8911, 9073, ... |
13 | 21, 85, 105, 561, 1099, 1785, 2465, 5149, 5185, 7107, 8841, 8911, 9577, 9637, ... |
14 | 15, 65, 481, 781, 793, 841, 985, 1541, 2257, 2465, 2561, 2743, 3277, 5185, 5713, 6533, 6541, 7171, 7449, 7585, 8321, 9073, ... |
15 | 341, 1477, 1541, 1687, 1729, 1921, 3277, 6541, 9073, ... |
16 | 15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ... |
17 | 9, 91, 145, 781, 1111, 1305, 1729, 2149, 2821, 4033, 4187, 5365, 5833, 6697, 7171, ... |
18 | 25, 49, 65, 133, 325, 343, 425, 1105, 1225, 1369, 1387, 1729, 1921, 2149, 2465, 2977, 4577, 5725, 5833, 5941, 6305, 6517, 6601, 7345, ... |
19 | 9, 45, 49, 169, 343, 561, 889, 905, 1105, 1661, 1849, 2353, 2465, 2701, 3201, 4033, 4681, 5461, 5713, 6541, 6697, 7957, 8145, 8281, 8401, 9997, ... |
20 | 21, 57, 133, 671, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2761, 3201, 5461, 5473, 5713, 5833, 6601, 6817, 7999, ... |
21 | 65, 221, 703, 793, 1045, 1105, 2465, 3781, 5185, 5473, 6541, 7363, 8965, 9061, ... |
22 | 21, 69, 91, 105, 161, 169, 345, 485, 1183, 1247, 1541, 1729, 2041, 2047, 2413, 2465, 2821, 3241, 3801, 5551, 7665, 9453, ... |
23 | 33, 169, 265, 341, 385, 481, 553, 1065, 1271, 1729, 2321, 2465, 2701, 2821, 3097, 4033, 4081, 4345, 4371, 4681, 5149, 6533, 6541, 7189, 7957, 8321, 8651, 8745, 8911, 9805, ... |
24 | 25, 175, 553, 805, 949, 1541, 1729, 1825, 1975, 2413, 2465, 2701, 3781, 4537, 6931, 7501, 9085, 9361, ... |
25 | 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... |
26 | 9, 25, 27, 45, 133, 217, 225, 475, 561, 589, 703, 925, 1065, 2465, 3325, 3385, 3565, 3825, 4741, 4921, 5041, 5425, 6697, 8029, 9073, ... |
27 | 65, 121, 133, 259, 341, 365, 481, 703, 1001, 1541, 1649, 1729, 1891, 2465, 2821, 2981, 2993, 3281, 4033, 4745, 4921, 4961, 5461, 6305, 6533, 7381, 7585, 8321, 8401, 8911, 9809, 9841, 9881, ... |
28 | 9, 27, 145, 261, 361, 529, 785, 1305, 1431, 2041, 2413, 2465, 3201, 3277, 4553, 4699, 5149, 7065, 8321, 8401, 9841, ... |
29 | 15, 21, 91, 105, 341, 469, 481, 793, 871, 1729, 1897, 2105, 2257, 2821, 4371, 4411, 5149, 5185, 5473, 5565, 6097, 7161, 8321, 8401, 8421, 8841, ... |
30 | 49, 133, 217, 341, 403, 469, 589, 637, 871, 901, 931, 1273, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 4081, 4097, 5729, 6031, 6061, 6097, 6409, 6817, 7657, 8023, 8029, 8401, 9881, ... |
Least Euler pseudoprime to base n[edit]
n | Least EPSP | n | Least EPSP | n | Least EPSP | n | Least EPSP |
1 | 9 | 33 | 545 | 65 | 33 | 97 | 21 |
2 | 341 | 34 | 21 | 66 | 65 | 98 | 9 |
3 | 121 | 35 | 9 | 67 | 33 | 99 | 25 |
4 | 341 | 36 | 35 | 68 | 25 | 100 | 9 |
5 | 217 | 37 | 9 | 69 | 35 | 101 | 25 |
6 | 185 | 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 | 65 | 44 | 9 | 76 | 15 | 108 | 91 |
13 | 21 | 45 | 133 | 77 | 39 | 109 | 9 |
14 | 15 | 46 | 9 | 78 | 77 | 110 | 111 |
15 | 341 | 47 | 65 | 79 | 39 | 111 | 55 |
16 | 15 | 48 | 49 | 80 | 9 | 112 | 65 |
17 | 9 | 49 | 25 | 81 | 91 | 113 | 21 |
18 | 25 | 50 | 21 | 82 | 9 | 114 | 115 |
19 | 9 | 51 | 25 | 83 | 21 | 115 | 57 |
20 | 21 | 52 | 51 | 84 | 85 | 116 | 9 |
21 | 65 | 53 | 9 | 85 | 21 | 117 | 49 |
22 | 21 | 54 | 55 | 86 | 65 | 118 | 9 |
23 | 33 | 55 | 9 | 87 | 133 | 119 | 15 |
24 | 25 | 56 | 33 | 88 | 87 | 120 | 77 |
25 | 217 | 57 | 25 | 89 | 9 | 121 | 15 |
26 | 9 | 58 | 57 | 90 | 91 | 122 | 33 |
27 | 65 | 59 | 15 | 91 | 9 | 123 | 85 |
28 | 9 | 60 | 341 | 92 | 21 | 124 | 25 |
29 | 15 | 61 | 15 | 93 | 25 | 125 | 9 |
30 | 49 | 62 | 9 | 94 | 57 | 126 | 25 |
31 | 15 | 63 | 341 | 95 | 141 | 127 | 9 |
32 | 25 | 64 | 9 | 96 | 65 | 128 | 49 |
See also[edit]
- Probable prime
References[edit]
^ ab Carl Pomerance; John L. Selfridge; Samuel S. Wagstaff, Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
- M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
- H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.
Categories:
- Pseudoprimes
(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.268","walltime":"0.354","ppvisitednodes":{"value":468,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":79892,"limit":2097152},"templateargumentsize":{"value":88,"limit":2097152},"expansiondepth":{"value":7,"limit":40},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":3260,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 179.817 1 -total"," 62.52% 112.430 1 Template:Reflist"," 54.36% 97.748 1 Template:Cite_journal"," 48.33% 86.899 7 Template:Navbox"," 35.00% 62.940 1 Template:Classes_of_natural_numbers"," 7.28% 13.094 1 Template:Icon"," 2.37% 4.262 1 Template:Rp"," 1.89% 3.396 1 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.093","limit":"10.000"},"limitreport-memusage":{"value":2654697,"limit":52428800}},"cachereport":{"origin":"mw1268","timestamp":"20181125222355","ttl":1900800,"transientcontent":false}}});mw.config.set({"wgBackendResponseTime":89,"wgHostname":"mw1273"});});