Skip to main content

Fermat pseudoprime









Fermat pseudoprime


From Wikipedia, the free encyclopedia

Jump to navigation
Jump to search


In number theory, the Fermat pseudoprimes make up the most important class of pseudoprimes that come from Fermat's little theorem.




Contents






  • 1 Definition


    • 1.1 Variations




  • 2 Properties


    • 2.1 Distribution


    • 2.2 Factorizations


    • 2.3 Smallest Fermat pseudoprimes


    • 2.4 List of Fermat pseudoprimes in fixed base n




  • 3 Which bases b make n a Fermat pseudoprime?


  • 4 Weak pseudoprimes


  • 5 Euler–Jacobi pseudoprimes


  • 6 Fermat primality test


  • 7 Applications


  • 8 References


  • 9 External links





Definition[edit]


Fermat's little theorem states that if p is prime and a is coprime to p, then ap−1 − 1 is divisible by p. For an integer a > 1, if a composite integer x divides ax−1 − 1, then x is called a Fermat pseudoprime to base a. In other words, a composite integer is a Fermat pseudoprime to base a if it successfully passes the Fermat primality test for the base a.[1] It follows that if x is a Fermat pseudoprime to base a, then x is coprime to a. [2]


The smallest base-2 Fermat pseudoprime is 341. It is not a prime, since it equals 11·31, but it satisfies Fermat's little theorem: 2340 ≡ 1 (mod 341) and thus passes the
Fermat primality test for the base 2.


Pseudoprimes to base 2 are sometimes called Poulet numbers, after the Belgian mathematician Paul Poulet, Sarrus numbers, or Fermatians (sequence A001567 in the OEIS).


A Fermat pseudoprime is often called a pseudoprime, with the modifier Fermat being understood.


An integer x that is a Fermat pseudoprime for all values of a that are coprime to x is called a Carmichael number.[1]



Variations[edit]


Some sources use variations of the definition, for example to only allow odd numbers to be pseudoprimes.[3]


Every odd number q satisfies aq−1≡1(modq){displaystyle a^{q-1}equiv 1{pmod {q}}}a^{q-1}equiv 1{pmod {q}} for a=q−1{displaystyle a=q-1}a=q-1. This trivial case is excluded in the definition of a Fermat pseudoprime given by Crandall and Pomerance:[4]


A composite number q is a Fermat pseudoprime to a base a, if aq-1 ≡ 1 mod q and a ≠ ±1 mod q.


Properties[edit]



Distribution[edit]


There are infinitely many pseudoprimes to a given base (in fact, infinitely many strong pseudoprimes (see Theorem 1 of
[5])
and infinitely many Carmichael numbers
[6])
, but they are rather rare.
There are only three pseudoprimes to base 2 below 1000, 245 below one million, and only 21853 less than 25·109 (see Table 1 of [5]).


Starting at 17·257, the product of consecutive Fermat numbers is a base-2 pseudoprime, and so are all Fermat composite and Mersenne composite.



Factorizations[edit]


The factorizations of the 60 Poulet numbers up to 60787, including 13 Carmichael numbers (in bold), are in the following table.


(sequence A001567 in the OEIS)








































































Poulet 1 to 15
341 11 · 31
561 3 · 11 · 17
645 3 · 5 · 43
1105 5 · 13 · 17
1387 19 · 73
1729 7 · 13 · 19
1905 3 · 5 · 127
2047 23 · 89
2465 5 · 17 · 29
2701 37 · 73
2821 7 · 13 · 31
3277 29 · 113
4033 37 · 109
4369 17 · 257
4371 3 · 31 · 47


































































Poulet 16 to 30
4681 31 · 151
5461 43 · 127
6601 7 · 23 · 41
7957 73 · 109
8321 53 · 157
8481 3 · 11 · 257
8911 7 · 19 · 67
10261 31 · 331
10585 5 · 29 · 73
11305 5 · 7 · 17 · 19
12801 3 · 17 · 251
13741 7 · 13 · 151
13747 59 · 233
13981 11 · 31 · 41
14491 43 · 337


































































Poulet 31 to 45
15709 23 · 683
15841 7 · 31 · 73
16705 5 · 13 · 257
18705 3 · 5 · 29 · 43
18721 97 · 193
19951 71 · 281
23001 3 · 11 · 17 · 41
23377 97 · 241
25761 3 · 31 · 277
29341 13 · 37 · 61
30121 7 · 13 · 331
30889 17 · 23 · 79
31417 89 · 353
31609 73 · 433
31621 103 · 307


































































Poulet 46 to 60
33153 3 · 43 · 257
34945 5 · 29 · 241
35333 89 · 397
39865 5 · 7 · 17 · 67
41041 7 · 11 · 13 · 41
41665 5 · 13 · 641
42799 127 · 337
46657 13 · 37 · 97
49141 157 · 313
49981 151 · 331
52633 7 · 73 · 103
55245 3 · 5 · 29 · 127
57421 7 · 13 · 631
60701 101 · 601
60787 89 · 683


A Poulet number all of whose divisors d divide 2d − 2 is called a super-Poulet number. There are infinitely many Poulet numbers which are not super-Poulet Numbers.[7]



Smallest Fermat pseudoprimes[edit]


The smallest pseudoprime for each base a ≤ 200 is given in the following table; the colors mark the number of prime factors. Unlike in the definition at the start of the article, pseudoprimes below a are excluded in the table. (For that to allow pseudoprimes below a, see OEIS: A090086)


(sequence A007535 in the OEIS)


































































































































































































































































































































































































































































































































a
smallest p-p

a
smallest p-p

a
smallest p-p

a
smallest p-p
1
4 = 2²
51
65 = 5 · 13
101
175 = 5² · 7
151
175 = 5² · 7
2
341 = 11 · 31
52
85 = 5 · 17
102
133 = 7 · 19
152
153 = 3² · 17
3
91 = 7 · 13
53
65 = 5 · 13
103
133 = 7 · 19
153
209 = 11 · 19
4
15 = 3 · 5
54
55 = 5 · 11
104
105 = 3 · 5 · 7
154
155 = 5 · 31
5
124 = 2² · 31
55
63 = 3² · 7
105
451 = 11 · 41
155
231 = 3 · 7 · 11
6
35 = 5 · 7
56
57 = 3 · 19
106
133 = 7 · 19
156
217 = 7 · 31
7
25 = 5²
57
65 = 5 · 13
107
133 = 7 · 19
157
186 = 2 · 3 · 31
8
9 = 3²
58
133 = 7 · 19
108
341 = 11 · 31
158
159 = 3 · 53
9
28 = 2² · 7
59
87 = 3 · 29
109
117 = 3² · 13
159
247 = 13 · 19
10
33 = 3 · 11
60
341 = 11 · 31
110
111 = 3 · 37
160
161 = 7 · 23
11
15 = 3 · 5
61
91 = 7 · 13
111
190 = 2 · 5 · 19
161
190 = 2 · 5 · 19
12
65 = 5 · 13
62
63 = 3² · 7
112
121 = 11²
162
481 = 13 · 37
13
21 = 3 · 7
63
341 = 11 · 31
113
133 = 7 · 19
163
186 = 2 · 3 · 31
14
15 = 3 · 5
64
65 = 5 · 13
114
115 = 5 · 23
164
165 = 3 · 5 · 11
15
341 = 11 · 31
65
112 = 2⁴ · 7
115
133 = 7 · 19
165
172 = 2² · 43
16
51 = 3 · 17
66
91 = 7 · 13
116
117 = 3² · 13
166
301 = 7 · 43
17
45 = 3² · 5
67
85 = 5 · 17
117
145 = 5 · 29
167
231 = 3 · 7 · 11
18
25 = 5²
68
69 = 3 · 23
118
119 = 7 · 17
168
169 = 13²
19
45 = 3² · 5
69
85 = 5 · 17
119
177 = 3 · 59
169
231 = 3 · 7 · 11
20
21 = 3 · 7
70
169 = 13²
120
121 = 11²
170
171 = 3² · 19
21
55 = 5 · 11
71
105 = 3 · 5 · 7
121
133 = 7 · 19
171
215 = 5 · 43
22
69 = 3 · 23
72
85 = 5 · 17
122
123 = 3 · 41
172
247 = 13 · 19
23
33 = 3 · 11
73
111 = 3 · 37
123
217 = 7 · 31
173
205 = 5 · 41
24
25 = 5²
74
75 = 3 · 5²
124
125 = 5³
174
175 = 5² · 7
25
28 = 2² · 7
75
91 = 7 · 13
125
133 = 7 · 19
175
319 = 11 · 19
26
27 = 3³
76
77 = 7 · 11
126
247 = 13 · 19
176
177 = 3 · 59
27
65 = 5 · 13
77
247 = 13 · 19
127
153 = 3² · 17
177
196 = 2² · 7²
28
45 = 3² · 5
78
341 = 11 · 31
128
129 = 3 · 43
178
247 = 13 · 19
29
35 = 5 · 7
79
91 = 7 · 13
129
217 = 7 · 31
179
185 = 5 · 37
30
49 = 7²
80
81 = 3⁴
130
217 = 7 · 31
180
217 = 7 · 31
31
49 = 7²
81
85 = 5 · 17
131
143 = 11 · 13
181
195 = 3 · 5 · 13
32
33 = 3 · 11
82
91 = 7 · 13
132
133 = 7 · 19
182
183 = 3 · 61
33
85 = 5 · 17
83
105 = 3 · 5 · 7
133
145 = 5 · 29
183
221 = 13 · 17
34
35 = 5 · 7
84
85 = 5 · 17
134
135 = 3³ · 5
184
185 = 5 · 37
35
51 = 3 · 17
85
129 = 3 · 43
135
221 = 13 · 17
185
217 = 7 · 31
36
91 = 7 · 13
86
87 = 3 · 29
136
265 = 5 · 53
186
187 = 11 · 17
37
45 = 3² · 5
87
91 = 7 · 13
137
148 = 2² · 37
187
217 = 7 · 31
38
39 = 3 · 13
88
91 = 7 · 13
138
259 = 7 · 37
188
189 = 3³ · 7
39
95 = 5 · 19
89
99 = 3² · 11
139
161 = 7 · 23
189
235 = 5 · 47
40
91 = 7 · 13
90
91 = 7 · 13
140
141 = 3 · 47
190
231 = 3 · 7 · 11
41
105 = 3 · 5 · 7
91
115 = 5 · 23
141
355 = 5 · 71
191
217 = 7 · 31
42
205 = 5 · 41
92
93 = 3 · 31
142
143 = 11 · 13
192
217 = 7 · 31
43
77 = 7 · 11
93
301 = 7 · 43
143
213 = 3 · 71
193
276 = 2² · 3 · 23
44
45 = 3² · 5
94
95 = 5 · 19
144
145 = 5 · 29
194
195 = 3 · 5 · 13
45
76 = 2² · 19
95
141 = 3 · 47
145
153 = 3² · 17
195
259 = 7 · 37
46
133 = 7 · 19
96
133 = 7 · 19
146
147 = 3 · 7²
196
205 = 5 · 41
47
65 = 5 · 13
97
105 = 3 · 5 · 7
147
169 = 13²
197
231 = 3 · 7 · 11
48
49 = 7²
98
99 = 3² · 11
148
231 = 3 · 7 · 11
198
247 = 13 · 19
49
66 = 2 · 3 · 11
99
145 = 5 · 29
149
175 = 5² · 7
199
225 = 3² · 5²
50
51 = 3 · 17
100
153 = 3² · 17
150
169 = 13²
200
201 = 3 · 67


List of Fermat pseudoprimes in fixed base n[edit]































































































































































n
First few Fermat pseudoprimes in base n

OEIS sequence
1
4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50, 51, 52, 54, 55, 56, 57, 58, 60, 62, 63, 64, 65, 66, 68, 69, 70, 72, 74, 75, 76, 77, 78, 80, 81, 82, 84, 85, 86, 87, 88, 90, 91, 92, 93, 94, 95, 96, 98, 99, 100, ... (All composites)

A002808
2
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...

A001567
3
91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...

A005935
4
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, ...

A020136
5
4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...

A005936
6
35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ...

A005937
7
6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...

A005938
8
9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, ...

A020137
9
4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, ...

A020138
10
9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, ...

A005939
11
10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, ...

A020139
12
65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073, ...

A020140
13
4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637, ...

A020141
14
15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073, ...

A020142
15
14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...

A020143
16
15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919, ...

A020144
17
4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, ...

A020145
18
25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061, ...

A020146
19
6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997, ...

A020147
20
21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911, ...

A020148
21
4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, ...

A020149
22
21, 69, 91, 105, 161, 169, 345, 483, 485, 645, 805, 1105, 1183, 1247, 1261, 1541, 1649, 1729, 1891, 2037, 2041, 2047, 2413, 2465, 2737, 2821, 3241, 3605, 3801, 5551, 5565, 5963, 6019, 6601, 6693, 7081, 7107, 7267, 7665, 8119, 8365, 8421, 8911, 9453, ...

A020150
23
22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027, 1045, 1065, 1105, 1183, 1271, 1729, 1738, 1749, 2059, 2321, 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651, 8745, 8911, 8965, 9805, ...

A020151
24
25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2701, 2737, 2821, 2885, 3781, 4207, 4537, 6601, 6931, 6943, 7081, 7189, 7471, 7501, 7813, 8725, 8911, 9085, 9361, 9809, ...

A020152
25
4, 6, 8, 12, 24, 28, 39, 66, 91, 124, 217, 232, 276, 403, 426, 451, 532, 561, 616, 703, 781, 804, 868, 946, 1128, 1288, 1541, 1729, 1891, 2047, 2701, 2806, 2821, 2911, 2926, 3052, 3126, 3367, 3592, 3976, 4069, 4123, 4207, 4564, 4636, 4686, 5321, 5461, 5551, 5611, 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9976, ...

A020153
26
9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 925, 1035, 1065, 1147, 2465, 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 8029, 8695, 8911, 9073, ...

A020154
27
26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1729, 1891, 2071, 2465, 2665, 2701, 2821, 2981, 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8911, 9139, 9709, 9809, 9841, 9881, 9919, ...

A020155
28
9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1305, 1413, 1431, 1885, 2041, 2413, 2465, 2871, 3201, 3277, 4553, 4699, 5149, 5181, 5365, 7065, 8149, 8321, 8401, 9841, ...

A020156
29
4, 14, 15, 21, 28, 35, 52, 91, 105, 231, 268, 341, 364, 469, 481, 561, 651, 793, 871, 1105, 1729, 1876, 1897, 2105, 2257, 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7294, 8321, 8401, 8421, 8841, 8911, ...

A020157
30
49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 3283, 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8401, 8911, 9881, ...

A020158

For more information (base 31 to 100), see OEIS: A020159 to OEIS: A020228, and for all bases up to 150, see table of Fermat pseudoprimes (text in German), this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n)



Which bases b make n a Fermat pseudoprime?[edit]


If composite n{displaystyle n}n is even, then n{displaystyle n}n is a Fermat pseudoprime to the trivial bases b≡1(modn){displaystyle bequiv 1{pmod {n}}}{displaystyle bequiv 1{pmod {n}}}.
If composite n{displaystyle n}n is odd, then n{displaystyle n}n is a Fermat pseudoprime to the trivial bases b≡±1(modn){displaystyle bequiv pm 1{pmod {n}}}{displaystyle bequiv pm 1{pmod {n}}}.


For any composite n{displaystyle n}n, the number of distinct bases b{displaystyle b}b modulo n{displaystyle n}n, for which n{displaystyle n}n is a Fermat pseudoprime base b{displaystyle b}b, is
[8]:Thm. 1, p. 1392


i=1kgcd(pi−1,n−1){displaystyle prod _{i=1}^{k}gcd(p_{i}-1,n-1)}{displaystyle prod _{i=1}^{k}gcd(p_{i}-1,n-1)}

where p1,…,pk{displaystyle p_{1},dots ,p_{k}}{displaystyle p_{1},dots ,p_{k}} are the distinct prime factors of n{displaystyle n}n. This includes the trivial bases.


For example, for n=341=11⋅31{displaystyle n=341=11cdot 31}{displaystyle n=341=11cdot 31}, this product is gcd(10,340)⋅gcd(30,340)=100{displaystyle gcd(10,340)cdot gcd(30,340)=100}{displaystyle gcd(10,340)cdot gcd(30,340)=100}. For n=341{displaystyle n=341}{displaystyle n=341}, the smallest such nontrivial base is b=2{displaystyle b=2}b=2.


Every odd composite n{displaystyle n}n is a Fermat pseudoprime to at least two nontrivial bases modulo n{displaystyle n}n unless n{displaystyle n}n is a power of 3.[8]:Cor. 1, p. 1393


For composite n < 200, the following is a table of all bases b < n which n is a Fermat pseudoprime. If a composite number n is not in the table (or n is in the sequence A209211), then n is a pseudoprime only to the trivial base 1 modulo n.


































































































































































































































































































































































n
bases b to which n is a Fermat pseudoprime (< n)
number of the bases of b (< n)
(sequence A063994 in the OEIS)
9
1, 8
2
15
1, 4, 11, 14
4
21
1, 8, 13, 20
4
25
1, 7, 18, 24
4
27
1, 26
2
28
1, 9, 25
3
33
1, 10, 23, 32
4
35
1, 6, 29, 34
4
39
1, 14, 25, 38
4
45
1, 8, 17, 19, 26, 28, 37, 44
8
49
1, 18, 19, 30, 31, 48
6
51
1, 16, 35, 50
4
52
1, 9, 29
3
55
1, 21, 34, 54
4
57
1, 20, 37, 56
4
63
1, 8, 55, 62
4
65
1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64
16
66
1, 25, 31, 37, 49
5
69
1, 22, 47, 68
4
70
1, 11, 51
3
75
1, 26, 49, 74
4
76
1, 45, 49
3
77
1, 34, 43, 76
4
81
1, 80
2
85
1, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 84
16
87
1, 28, 59, 86
4
91
1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48,
51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90
36
93
1, 32, 61, 92
4
95
1, 39, 56, 94
4
99
1, 10, 89, 98
4
105
1, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 104
16
111
1, 38, 73, 110
4
112
1, 65, 81
3
115
1, 24, 91, 114
4
117
1, 8, 44, 53, 64, 73, 109, 116
8
119
1, 50, 69, 118
4
121
1, 3, 9, 27, 40, 81, 94, 112, 118, 120
10
123
1, 40, 83, 122
4
124
1, 5, 25
3
125
1, 57, 68, 124
4
129
1, 44, 85, 128
4
130
1, 61, 81
3
133
1, 8, 11, 12, 18, 20, 26, 27, 30, 31, 37, 39, 45, 46, 50, 58, 64, 65, 68,
69, 75, 83, 87, 88, 94, 96, 102, 103, 106, 107, 113, 115, 121, 122, 125, 132
36
135
1, 26, 109, 134
4
141
1, 46, 95, 140
4
143
1, 12, 131, 142
4
145
1, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 144
16
147
1, 50, 97, 146
4
148
1, 121, 137
3
153
1, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 152
16
154
1, 23, 67
3
155
1, 61, 94, 154
4
159
1, 52, 107, 158
4
161
1, 22, 139, 160
4
165
1, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 164
16
169
1, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 168
12
171
1, 37, 134, 170
4
172
1, 49, 165
3
175
1, 24, 26, 51, 74, 76, 99, 101, 124, 149, 151, 174
12
176
1, 49, 81, 97, 113
5
177
1, 58, 119, 176
4
183
1, 62, 121, 182
4
185
1, 6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179, 184
16
186
1, 97, 109, 157, 163
5
187
1, 67, 120, 186
4
189
1, 55, 134, 188
4
190
1, 11, 61, 81, 101, 111, 121, 131, 161
9
195
1, 14, 64, 79, 116, 131, 181, 194
8
196
1, 165, 177
3

For more information (n = 201 to 5000), see,[9] this page does not define n is a pseudoprime to a base congruent to 1 or -1 (mod n). Note that when p is a prime, p2 is a Fermat pseudoprime to base b if and only if p is a Wieferich prime to base b. For example, 10932 = 1194649 is a Fermat pseudoprime to base 2, and 112 = 121 is a Fermat pseudoprime to base 3.


The number of the values of b for n are (For n prime, the number of the values of b must be n - 1, since all b satisfy the Fermat little theorem)


1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (sequence A063994 in the OEIS)

The least base b > 1 which n is a pseudoprime to base b (or prime number) are


2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (sequence A105222 in the OEIS)

The number of the values of b for n must divides φ{displaystyle varphi }varphi (n), or A000010(n) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... (The quotient can be any natural number, and the quotient = 1 if and only if n is a prime or a Carmichael number (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997), the quotient = 2 if and only if n is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311)


The least number with n values of b are (or 0 if no such number exists)


1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (sequence A064234 in the OEIS) (if and only if n is even and not totient of squarefree number, then the nth term of this sequence is 0)


Weak pseudoprimes[edit]


A composite number n which satisfy that bn≡b(modn){displaystyle b^{n}equiv b{pmod {n}}}{displaystyle b^{n}equiv b{pmod {n}}} is called weak pseudoprime to base b. A pseudoprime to base a (under the usual definition) satisfies this condition. Conversely, a weak pseudoprime that's coprime with the base is a pseudoprime in the usual sense, otherwise this may or may not be the case. [10] The least weak pseudoprime to base b = 1, 2, ... are:


4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... (sequence A000790 in the OEIS)

Note that all terms are less than or equal to the smallest Carmichael number, 561. Except for 561, only semiprimes can occur in the above sequence, but not all semiprimes less than 561 occur, a semiprime pq (pq) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see OEIS: A108574) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) (OEIS: A090086) is also usually semiprime, the first counterexample is A090086(648) = 385 = 5 × 7 × 11.


If we require n > b, they are (for b = 1, 2, ...)


4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... (sequence A239293 in the OEIS)

Carmichael numbers are weak pseudoprimes to all bases.


The smallest even weak pseudoprime in base 2 is 161038 (see OEIS: A006935).



Euler–Jacobi pseudoprimes[edit]



Another approach is to use more refined notions of pseudoprimality, e.g. strong pseudoprimes or Euler–Jacobi pseudoprimes, for which there are no analogues of Carmichael numbers. This leads to probabilistic algorithms such as the Solovay–Strassen primality test, the Baillie-PSW primality test, and the Miller–Rabin primality test, which produce what are known as industrial-grade primes. Industrial-grade primes are integers for which primality has not been "certified" (i.e. rigorously proven), but have undergone a test such as the Miller–Rabin test which has nonzero, but arbitrarily low, probability of failure.



Fermat primality test[edit]


Like the Lucas primality test, for a large number n (we assume that n is odd and nonsquare, or we can know that n is composite), we can choose the smallest positive integer b such that (bn)=−1{displaystyle left({tfrac {b}{n}}right)=-1}{displaystyle left({tfrac {b}{n}}right)=-1} (where (bn){displaystyle left({tfrac {b}{n}}right)}{displaystyle left({tfrac {b}{n}}right)} is the Jacobi symbol) as the base and use Fermat test, Euler-Jacobi test or Miller-Rabin test to test the primality of n. (If b and n have a prime factor in common, then (bn)=0{displaystyle left({tfrac {b}{n}}right)=0}{displaystyle left({tfrac {b}{n}}right)=0}, and if we found such b, then we can know that n is composite).


(This search will never succeed if n is square, and conversely if it does succeed, that is proof that n is not square. Thus, some time can be saved by delaying testing n for squareness until after the first few search steps have all failed.)


When use this test, the first few Fermat pseudoprimes are


217, 341, 561, 645, 703, 1105, 1387, 1729, 1825, 2465, 2701, 2821, 3277, 3281, 3367, 3751, 4371, 4961, 5461, 5551, 6601, 7957, 8911, 10225, 10261, 10585, 11521, 12025, 13741, 13747, 13981, 14089, 14383, 14491, 15709, 15841, 16297, 16471, 18721, 20425, 22945, 24727, 29341, 30673, 30857, 31621, 31697, 32791, 35333, 35425, 38503, 39865, 41041, 41329, 44287, 46657, 46999, 49105, 49141, 49321, 49981, ...

The first few Euler pseudoprimes are


217, 341, 561, 703, 1729, 1825, 2465, 3277, 3281, 4961, 5461, 8911, 10225, 10261, 11521, 12025, 14089, 15709, 15841, 16297, 20425, 29341, 30673, 30857, 31621, 31697, 35425, 39865, 41041, 41329, 44287, 46657, 49105, 49141, 49321, 49981, 50881, 54145, 65077, 68401, 72041, 75241, 75361, 80581, 83333, 88357, 88705, 96049, 96985, 97567, 97921, ...

The first few Euler-Jacobi pseudoprimes are


703, 3277, 3281, 8911, 14089, 29341, 44287, 49141, 80581, 88357, 97567, 102311, 104653, 121463, 152551, 172369, 173951, 182527, 188191, 195313, 196093, 216457, 218791, 304921, 313447, 314821, 320167, 364231, 410041, 458989, 476971, 489997, 491209, 497503, 658711, 665281, 721801, 777961, 800605, 838861, 859951, 873181, 877099, 973241, ...

The first few strong pseudoprimes are


703, 3277, 3281, 8911, 14089, 29341, 44287, 49141, 80581, 88357, 97567, 102311, 104653, 121463, 152551, 172369, 173951, 182527, 188191, 195313, 196093, 216457, 218791, 304921, 313447, 314821, 320167, 364231, 410041, 458989, 476971, 489997, 491209, 497503, 658711, 665281, 721801, 777961, 800605, 838861, 859951, 873181, 877099, 973241, ...


























Test
Fermat primality test
Lucas primality test
Condition of the number n

n is odd and nonsquare
Choose base b (for Fermat) or Lucas parameters (P, Q) (for Lucas)

b is the first number in the sequence 2, 3, 4, 5, 6, 7, 8, ... such that (bn)=−1{displaystyle left({tfrac {b}{n}}right)=-1}{displaystyle left({tfrac {b}{n}}right)=-1} (where (bn){displaystyle left({tfrac {b}{n}}right)}{displaystyle left({tfrac {b}{n}}right)} is the Jacobi symbol)

P = 1, Q is the first number in the sequence −1, 2, −2, 3, −3, 4, −4, ... such that (1−4Qn)=−1{displaystyle left({tfrac {1-4Q}{n}}right)=-1}{displaystyle left({tfrac {1-4Q}{n}}right)=-1} (where (1−4Qn){displaystyle left({tfrac {1-4Q}{n}}right)}{displaystyle left({tfrac {1-4Q}{n}}right)} is the Jacobi symbol)
The first few pseudoprimes
217, 341, 561, 645, 703, 1105, 1387, 1729, 1825, 2465, 2701, 2821, 3277, 3281, 3367, 3751, 4371, 4961, 5461, 5551, 6601, 7957, 8911
323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179
The first few strong pseudoprimes
703, 3277, 3281, 8911, 14089, 29341, 44287, 49141, 80581, 88357, 97567
5459, 5777, 10877, 16109, 18971, 22499, 24569, 25199, 40309, 58519, 75077, 97439

It is conjectured that there is no composite number that passes both the strong (Fermat) primality test and the strong Lucas primality test.



Applications[edit]


The rarity of such pseudoprimes has important practical implications. For example, public-key cryptography algorithms such as RSA require the ability to quickly find large primes. The usual algorithm to generate prime numbers is to generate random odd numbers and test them for primality. However, deterministic primality tests are slow. If the user is willing to tolerate an arbitrarily small chance that the number found is not a prime number but a pseudoprime, it is possible to use the much faster and simpler Fermat primality test.



References[edit]





  1. ^ ab Desmedt, Yvo (2010). "Encryption Schemes". In Atallah, Mikhail J.; Blanton, Marina. Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10–23. ISBN 978-1-58488-820-8..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}


  2. ^ "Contrapositive of this statement on math.stackexchange".


  3. ^ Weisstein, Eric W. "Fermat Pseudoprime". MathWorld.


  4. ^ Crandall, Richard; Pomerance, Carl (2001). "Theorem 3.4.2". Prime Numbers – A Computational Perspective. Springer-Verlag. p. 132.


  5. ^ ab Pomerance, Carl; Selfridge, John L.; Wagstaff, Samuel S., Jr. (July 1980). "The pseudoprimes to 25·109" (PDF). Mathematics of Computation. 35 (151): 1003–1026. doi:10.1090/S0025-5718-1980-0572872-7.


  6. ^ Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics. 140: 703–722. doi:10.2307/2118576.


  7. ^ Sierpinski, W. (1988-02-15), "Chapter V.7", in Ed. A. Schinzel, Elementary Theory of Numbers, North-Holland Mathematical Library (2 Sub ed.), Amsterdam: North Holland, p. 232, ISBN 9780444866622


  8. ^ ab Robert Baillie; Samuel S. Wagstaff Jr. (October 1980). "Lucas Pseudoprimes" (PDF). Mathematics of Computation. 35 (152): 1391–1417. doi:10.1090/S0025-5718-1980-0583518-6. MR 0583518.


  9. ^ "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher". de.m.wikibooks.org. Retrieved 21 April 2018.


  10. ^ Michon, Gerard. "Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality - Numericana". www.numericana.com. Retrieved 21 April 2018.




External links[edit]



  • W. F. Galway and Jan Feitsma, Tables of pseudoprimes and related data (comprehensive list of all pseudoprimes below 264, including factorization, strong pseudoprimes, and Carmichael numbers)

  • A research for pseudoprime











Retrieved from "https://en.wikipedia.org/w/index.php?title=Fermat_pseudoprime&oldid=858130690"





Navigation menu

























(window.RLQ=window.RLQ||).push(function(){mw.config.set({"wgPageParseReport":{"limitreport":{"cputime":"0.436","walltime":"0.772","ppvisitednodes":{"value":1724,"limit":1000000},"ppgeneratednodes":{"value":0,"limit":1500000},"postexpandincludesize":{"value":101228,"limit":2097152},"templateargumentsize":{"value":1664,"limit":2097152},"expansiondepth":{"value":7,"limit":40},"expensivefunctioncount":{"value":2,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":29159,"limit":5000000},"entityaccesscount":{"value":2,"limit":400},"timingprofile":["100.00% 299.325 1 -total"," 60.37% 180.708 1 Template:Reflist"," 23.89% 71.498 2 Template:Cite_book"," 18.70% 55.968 7 Template:Navbox"," 17.02% 50.953 3 Template:Cite_journal"," 14.59% 43.665 1 Template:Classes_of_natural_numbers"," 10.34% 30.959 1 Template:Main"," 6.64% 19.879 4 Template:Cite_web"," 3.49% 10.452 1 Template:Citation"," 3.21% 9.623 1 Template:Icon"]},"scribunto":{"limitreport-timeusage":{"value":"0.138","limit":"10.000"},"limitreport-memusage":{"value":3679825,"limit":52428800}},"cachereport":{"origin":"mw1320","timestamp":"20181125223522","ttl":1900800,"transientcontent":false}}});mw.config.set({"wgBackendResponseTime":93,"wgHostname":"mw1246"});});

Popular posts from this blog

Florida Star v. B. J. F.

Danny Elfman

Lugert, Oklahoma