请输入您要查询的百科知识：

　

词条 Fermat pseudoprime
释义

  1. Definition

      Variations  

  2. Properties

     Distribution  Factorizations   Smallest Fermat pseudoprimes    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

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

Definition

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 {{OEIS|id=A001567}}.

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

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

Every odd number q satisfies for . 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 {{math|aq-1 ≡ 1 mod q}} and {{math|a ≠ ±1 mod q}}.

Properties

Distribution

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

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

{{OEIS|id=A001567}}
Poulet 1 to 15
34111 · 31
5613 · 11 · 17
6453 · 5 · 43
11055 · 13 · 17
138719 · 73
17297 · 13 · 19
19053 · 5 · 127
204723 · 89
24655 · 17 · 29
270137 · 73
28217 · 13 · 31
327729 · 113
403337 · 109
436917 · 257
43713 · 31 · 47
Poulet 16 to 30
468131 · 151
546143 · 127
66017 · 23 · 41
795773 · 109
832153 · 157
84813 · 11 · 257
89117 · 19 · 67
1026131 · 331
105855 · 29 · 73
113055 · 7 · 17 · 19
128013 · 17 · 251
137417 · 13 · 151
1374759 · 233
1398111 · 31 · 41
1449143 · 337
Poulet 31 to 45
1570923 · 683
158417 · 31 · 73
167055 · 13 · 257
187053 · 5 · 29 · 43
1872197 · 193
1995171 · 281
230013 · 11 · 17 · 41
2337797 · 241
257613 · 31 · 277
2934113 · 37 · 61
301217 · 13 · 331
3088917 · 23 · 79
3141789 · 353
3160973 · 433
31621103 · 307
Poulet 46 to 60
331533 · 43 · 257
349455 · 29 · 241
3533389 · 397
398655 · 7 · 17 · 67
410417 · 11 · 13 · 41
416655 · 13 · 641
42799127 · 337
4665713 · 37 · 97
49141157 · 313
49981151 · 331
526337 · 73 · 103
552453 · 5 · 29 · 127
574217 · 13 · 631
60701101 · 601
6078789 · 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

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|id=A090086}})

{{OEIS|id=A007535}}
a smallest p-p a smallest p-p a smallest p-p a smallest p-p
14 = 2² 51 65 = 5 · 13101175 = 5² · 7151175 = 5² · 7
2 341 = 11 · 31 52 85 = 5 · 17 102 133 = 7 · 19152153 = 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 · 11104105 = 3 · 5 · 7 154 155 = 5 · 31
5124 = 2² · 315563 = 3² · 7 105 451 = 11 · 41155231 = 3 · 7 · 11
6 35 = 5 · 7 56 57 = 3 · 19 106 133 = 7 · 19 156 217 = 7 · 31
725 = 5² 57 65 = 5 · 13 107 133 = 7 · 19157186 = 2 · 3 · 31
89 = 3² 58 133 = 7 · 19 108 341 = 11 · 31 158 159 = 3 · 53
928 = 2² · 7 59 87 = 3 · 29109117 = 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 · 13111190 = 2 · 5 · 19161190 = 2 · 5 · 19
12 65 = 5 · 136263 = 3² · 7112121 = 11² 162 481 = 13 · 37
13 21 = 3 · 7 63 341 = 11 · 31 113 133 = 7 · 19163186 = 2 · 3 · 31
14 15 = 3 · 5 64 65 = 5 · 13 114 115 = 5 · 23164165 = 3 · 5 · 11
15 341 = 11 · 3165112 = 2⁴ · 7 115 133 = 7 · 19165172 = 2² · 43
16 51 = 3 · 17 66 91 = 7 · 13116117 = 3² · 13 166 301 = 7 · 43
1745 = 3² · 5 67 85 = 5 · 17 117 145 = 5 · 29167231 = 3 · 7 · 11
1825 = 5² 68 69 = 3 · 23 118 119 = 7 · 17168169 = 13²
1945 = 3² · 5 69 85 = 5 · 17 119 177 = 3 · 59169231 = 3 · 7 · 11
20 21 = 3 · 770169 = 13²120121 = 11²170171 = 3² · 19
21 55 = 5 · 1171105 = 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
2425 = 5²7475 = 3 · 5²124125 = 5³174175 = 5² · 7
2528 = 2² · 7 75 91 = 7 · 13 125 133 = 7 · 19 175 319 = 11 · 19
2627 = 3³ 76 77 = 7 · 11 126 247 = 13 · 19 176 177 = 3 · 59
27 65 = 5 · 13 77 247 = 13 · 19127153 = 3² · 17177196 = 2² · 7²
2845 = 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
3049 = 7²8081 = 3⁴ 130 217 = 7 · 31 180 217 = 7 · 31
3149 = 7² 81 85 = 5 · 17 131 143 = 11 · 13181195 = 3 · 5 · 13
32 33 = 3 · 11 82 91 = 7 · 13 132 133 = 7 · 19 182 183 = 3 · 61
33 85 = 5 · 1783105 = 3 · 5 · 7 133 145 = 5 · 29 183 221 = 13 · 17
34 35 = 5 · 7 84 85 = 5 · 17134135 = 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
3745 = 3² · 5 87 91 = 7 · 13137148 = 2² · 37 187 217 = 7 · 31
38 39 = 3 · 13 88 91 = 7 · 13 138 259 = 7 · 37188189 = 3³ · 7
39 95 = 5 · 198999 = 3² · 11 139 161 = 7 · 23 189 235 = 5 · 47
40 91 = 7 · 13 90 91 = 7 · 13 140 141 = 3 · 47190231 = 3 · 7 · 11
41105 = 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 · 71193276 = 2² · 3 · 23
4445 = 3² · 5 94 95 = 5 · 19 144 145 = 5 · 29194195 = 3 · 5 · 13
4576 = 2² · 19 95 141 = 3 · 47145153 = 3² · 17 195 259 = 7 · 37
46 133 = 7 · 19 96 133 = 7 · 19146147 = 3 · 7² 196 205 = 5 · 41
47 65 = 5 · 1397105 = 3 · 5 · 7147169 = 13²197231 = 3 · 7 · 11
4849 = 7²9899 = 3² · 11148231 = 3 · 7 · 11 198 247 = 13 · 19
4966 = 2 · 3 · 11 99 145 = 5 · 29149175 = 5² · 7199225 = 3² · 5²
50 51 = 3 · 17100153 = 3² · 17150169 = 13² 200 201 = 3 · 67

List of Fermat pseudoprimes in fixed base n

nFirst few Fermat pseudoprimes in base nOEIS sequence
14, 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)id=A002808}}
2341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...id=A001567}}
391, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...id=A005935}}
415, 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, ...id=A020136}}
54, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...id=A005936}}
635, 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, ...id=A005937}}
76, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...id=A005938}}
89, 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, ...id=A020137}}
94, 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, ...id=A020138}}
109, 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, ...id=A005939}}
1110, 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, ...id=A020139}}
1265, 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, ...id=A020140}}
134, 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, ...id=A020141}}
1415, 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, ...id=A020142}}
1514, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...id=A020143}}
1615, 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, ...id=A020144}}
174, 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, ...id=A020145}}
1825, 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, ...id=A020146}}
196, 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, ...id=A020147}}
2021, 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, ...id=A020148}}
214, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, ...id=A020149}}
2221, 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, ...id=A020150}}
2322, 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, ...id=A020151}}
2425, 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, ...id=A020152}}
254, 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, ...id=A020153}}
269, 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, ...id=A020154}}
2726, 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, ...id=A020155}}
289, 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, ...id=A020156}}
294, 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, ...id=A020157}}
3049, 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, ...id=A020158}}

For more information (base 31 to 100), see {{oeis|id=A020159}} to {{oeis|id=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?

If composite is even, then is a Fermat pseudoprime to the trivial bases .

If composite is odd, then is a Fermat pseudoprime to the trivial bases .

For any composite , the number of distinct bases modulo , for which is a Fermat pseudoprime base , is

[8]{{rp|Thm. 1, p. 1392}}

where are the distinct prime factors of . This includes the trivial bases.

For example, for , this product is . For , the smallest such nontrivial base is .

Every odd composite is a Fermat pseudoprime to at least two nontrivial bases modulo unless is a power of 3.[8]{{rp|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 {{OEIS link|id=A209211}}), then n is a pseudoprime only to the trivial base 1 modulo n.

nbases b to which n is a Fermat pseudoprime (< n)b (< n)
{{OEIS>id=A063994}}
91, 82
151, 4, 11, 144
211, 8, 13, 204
251, 7, 18, 244
271, 262
281, 9, 253
331, 10, 23, 324
351, 6, 29, 344
391, 14, 25, 384
451, 8, 17, 19, 26, 28, 37, 448
491, 18, 19, 30, 31, 486
511, 16, 35, 504
521, 9, 293
551, 21, 34, 544
571, 20, 37, 564
631, 8, 55, 624
651, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 6416
661, 25, 31, 37, 495
691, 22, 47, 684
701, 11, 513
751, 26, 49, 744
761, 45, 493
771, 34, 43, 764
811, 802
851, 4, 13, 16, 18, 21, 33, 38, 47, 52, 64, 67, 69, 72, 81, 8416
871, 28, 59, 864
911, 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
931, 32, 61, 924
951, 39, 56, 944
991, 10, 89, 984
1051, 8, 13, 22, 29, 34, 41, 43, 62, 64, 71, 76, 83, 92, 97, 10416
1111, 38, 73, 1104
1121, 65, 813
1151, 24, 91, 1144
1171, 8, 44, 53, 64, 73, 109, 1168
1191, 50, 69, 1184
1211, 3, 9, 27, 40, 81, 94, 112, 118, 12010
1231, 40, 83, 1224
1241, 5, 253
1251, 57, 68, 1244
1291, 44, 85, 1284
1301, 61, 813
1331, 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
1351, 26, 109, 1344
1411, 46, 95, 1404
1431, 12, 131, 1424
1451, 12, 17, 28, 41, 46, 57, 59, 86, 88, 99, 104, 117, 128, 133, 14416
1471, 50, 97, 1464
1481, 121, 1373
1531, 8, 19, 26, 35, 53, 55, 64, 89, 98, 100, 118, 127, 134, 145, 15216
1541, 23, 673
1551, 61, 94, 1544
1591, 52, 107, 1584
1611, 22, 139, 1604
1651, 23, 32, 34, 43, 56, 67, 76, 89, 98, 109, 122, 131, 133, 142, 16416
1691, 19, 22, 23, 70, 80, 89, 99, 146, 147, 150, 16812
1711, 37, 134, 1704
1721, 49, 1653
1751, 24, 26, 51, 74, 76, 99, 101, 124, 149, 151, 17412
1761, 49, 81, 97, 1135
1771, 58, 119, 1764
1831, 62, 121, 1824
1851, 6, 31, 36, 38, 43, 68, 73, 112, 117, 142, 147, 149, 154, 179, 18416
1861, 97, 109, 157, 1635
1871, 67, 120, 1864
1891, 55, 134, 1884
1901, 11, 61, 81, 101, 111, 121, 131, 1619
1951, 14, 64, 79, 116, 131, 181, 1948
1961, 165, 1773

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, ... {{OEIS|id=A063994}}

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, ... {{OEIS|id=A105222}}

The number of the values of b for n must divides (n), or {{OEIS link|id=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, ... {{OEIS link|id=A002997}}), the quotient = 2 if and only if n is in the sequence: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... {{OEIS link|id=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, ... {{OEIS|id=A064234}} (if and only if n is even and not totient of squarefree number, then the nth term of this sequence is 0)

Weak pseudoprimes

A composite number n which satisfy that 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, ... {{OEIS|id=A000790}}

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 (p ≤ q) less than 561 occurs in the above sequences if and only if p − 1 divides q − 1. (see {{oeis|id=A108574}}) Besides, the smallest pseudoprime to base n (also not necessary exceeding n) ({{oeis|A090086}}) is also usually semiprime, the first counterexample is {{OEIS link|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, ... {{OEIS|id=A239293}}

Carmichael numbers are weak pseudoprimes to all bases.

The smallest even weak pseudoprime in base 2 is 161038 (see {{oeis|id=A006935}}).

Euler–Jacobi pseudoprimes

{{main|Euler–Jacobi pseudoprime}}

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

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 (where 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 , 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, ...

TestFermat primality testLucas primality test
Condition of the number nn 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 (where is the Jacobi symbol)P = 1, Q is the first number in the sequence −1, 2, −2, 3, −3, 4, −4, ... such that (where is the Jacobi symbol)
The first few pseudoprimes217, 341, 561, 645, 703, 1105, 1387, 1729, 1825, 2465, 2701, 2821, 3277, 3281, 3367, 3751, 4371, 4961, 5461, 5551, 6601, 7957, 8911323, 377, 1159, 1829, 3827, 5459, 5777, 9071, 9179
The first few strong pseudoprimes703, 3277, 3281, 8911, 14089, 29341, 44287, 49141, 80581, 88357, 975675459, 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

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

1. ^1 {{cite book |last=Desmedt |first=Yvo |editor1-last=Atallah |editor1-first=Mikhail J. |editor1-link=Mikhail Atallah |editor2-last=Blanton |editor2-first=Marina |year=2010 |title=Algorithms and theory of computation handbook: Special topics and techniques |chapter=Encryption Schemes |publisher=CRC Press |isbn=978-1-58488-820-8 |pages=10–23 |chapter-url=https://books.google.com/books?id=SbPpg_4ZRGsC&pg=SA10-PA23}}
2. ^{{cite web | url=https://math.stackexchange.com/questions/320967/if-n-geq-1-is-not-prime-and-x-in-mathbbz-n-such-that-gcdx-n-neq-1?rq=1 |title = Contrapositive of this statement on math.stackexchange}}
3. ^{{MathWorld|title=Fermat Pseudoprime|urlname=FermatPseudoprime}}
4. ^{{cite book |last1=Crandall |first1=Richard |authorlink1=Richard Crandall |last2=Pomerance |first2=Carl |authorlink2=Carl Pomerance |year=2001 |title=Prime Numbers – A Computational Perspective |chapter=Theorem 3.4.2 |publisher=Springer-Verlag |page=132}}
5. ^1 {{cite journal |last1=Pomerance |first1=Carl |authorlink1=Carl Pomerance |last2=Selfridge |first2=John L. |authorlink2=John L. Selfridge |last3=Wagstaff |first3=Samuel S., Jr. |authorlink3=Samuel S. Wagstaff Jr. |date=July 1980 |title=The pseudoprimes to 25·109 |journal=Mathematics of Computation |doi=10.1090/S0025-5718-1980-0572872-7 |volume=35 |issue=151 |pages=1003–1026 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf }}
6. ^{{cite journal |last1=Alford |first1=W. R. |authorlink=W. R. (Red) Alford |last2=Granville |first2=Andrew |authorlink2=Andrew Granville |last3=Pomerance |first3=Carl |authorlink3=Carl Pomerance |year=1994 |title=There are Infinitely Many Carmichael Numbers |journal=Annals of Mathematics |doi=10.2307/2118576 |volume=140 |issue=3 |pages=703–722 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper95.pdf |jstor=2118576 }}
7. ^{{Citation|date = 1988-02-15|edition = 2 Sub|isbn = 9780444866622|location = Amsterdam|publisher = North Holland|title = Elementary Theory of Numbers|first = W.|last = Sierpinski|chapter = Chapter V.7|page = 232|series = North-Holland Mathematical Library|editor = Ed. A. Schinzel }}
8. ^1 {{cite journal |author=Robert Baillie |author2=Samuel S. Wagstaff Jr.|title=Lucas Pseudoprimes|journal=Mathematics of Computation|date=October 1980|volume=35|issue=152|pages=1391–1417|url=http://mpqs.free.fr/LucasPseudoprimes.pdf| mr=583518| doi=10.1090/S0025-5718-1980-0583518-6 }}
9. ^{{cite web|url=http://de.m.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_(15_-_4999)|title=Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) – Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher|author=|date=|website=de.m.wikibooks.org|accessdate=21 April 2018}}
10. ^{{cite web|url=http://www.numericana.com/answer/pseudo.htm#weak|title=Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality - Numericana|first=Gerard|last=Michon|date=|website=www.numericana.com|accessdate=21 April 2018}}

External links

{{Classes of natural numbers}}

2 : Pseudoprimes|Asymmetric-key algorithms

随便看

　

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

　

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间：2024/11/12 13:03:02