|
欧拉伪素数（英語：Euler pseudoprime）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果
成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。
与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 = 1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q+1) − 1 = 1 (mod p) 成立。再进一步化简为a2q − 1 = 0 (mod p)。通过因式分解，得到(aq − 1)(aq + 1) = 0 (mod p)，即a(p−1)/2 = ±1 (mod p)。
上式可以用作概率素性检验，其可靠性是费马素性检验的两倍。不过无法基于欧拉伪素数对素数进行确定性检验，因为存在绝对欧拉伪素数，即其关于所有与其互素的数都是欧拉伪素数。绝对欧拉伪素数是卡迈克尔数（即绝对费马伪素数）的子集。最小的绝对欧拉伪素数为1729 = 7×13×19。
示例
| n
|
关于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, ...
|
| 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, ...
|
关于n的最小欧拉伪素数
| n
|
最小欧拉伪素数
|
n
|
最小欧拉伪素数
|
n
|
最小欧拉伪素数
|
n
|
最小欧拉伪素数
|
| 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
|
参见
参考文献
- 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.
|