Fermat pseudoprime

Last updated

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

Contents

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 a positive integer a, if a composite integer x divides ax−1  1, then x is called a Fermat pseudoprime to base a. [1] :Def. 3.32 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. [2] The false statement that all numbers that pass the Fermat primality test for base 2 are prime is called the Chinese hypothesis.

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 Sarrus numbers, after P. F. Sarrus who discovered that 341 has this property, Poulet numbers, after P. Poulet who made a table of such 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. [2] [1] :Def. 3.34

Properties

Distribution

There are infinitely many pseudoprimes to any given base a > 1. In 1904, Cipolla showed how to produce an infinite number of pseudoprimes to base a > 1: let A = (ap - 1)/(a - 1) and let B = (ap + 1)/(a + 1), where p is a prime number that does not divide a(a2 - 1). Then n = AB is composite, and is a pseudoprime to base a. [3] [4] For example, if a = 2 and p = 5, then A = 31, B = 11, and n = 341 is a pseudoprime to base 2.

In fact, there are infinitely many strong pseudoprimes to any base greater than 1 (see Theorem 1 of [5] ) and infinitely many Carmichael numbers, [6] but they are comparatively rare. There are three pseudoprimes to base 2 below 1000, 245 below one million, and 21853 less than 25·109. There are 4842 strong pseudoprimes base 2 and 2163 Carmichael numbers below this limit (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 composites and Mersenne composites.

The probability of a composite number n passing the Fermat test approaches zero for . Specifically, Kim and Pomerance showed the following: The probability that a random odd number n ≤ x is a Fermat pseudoprime to a random base is less than 2.77·10-8 for x= 10100, and is at most (log x)-197<10-10,000 for x≥10100,000. [7]

Factorizations

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
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. [8]

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:  A090086 )

(sequence A007535 in the OEIS )

asmallest p-pasmallest p-pasmallest p-pasmallest p-p
14 = 2²5165 = 5 · 13101175 = 5² · 7151175 = 5² · 7
2341 = 11 · 315285 = 5 · 17102133 = 7 · 19152153 = 3² · 17
391 = 7 · 135365 = 5 · 13103133 = 7 · 19153209 = 11 · 19
415 = 3 · 55455 = 5 · 11104105 = 3 · 5 · 7154155 = 5 · 31
5124 = 2² · 315563 = 3² · 7105451 = 11 · 41155231 = 3 · 7 · 11
635 = 5 · 75657 = 3 · 19106133 = 7 · 19156217 = 7 · 31
725 = 5²5765 = 5 · 13107133 = 7 · 19157186 = 2 · 3 · 31
89 = 3²58133 = 7 · 19108341 = 11 · 31158159 = 3 · 53
928 = 2² · 75987 = 3 · 29109117 = 3² · 13159247 = 13 · 19
1033 = 3 · 1160341 = 11 · 31110111 = 3 · 37160161 = 7 · 23
1115 = 3 · 56191 = 7 · 13111190 = 2 · 5 · 19161190 = 2 · 5 · 19
1265 = 5 · 136263 = 3² · 7112121 = 11²162481 = 13 · 37
1321 = 3 · 763341 = 11 · 31113133 = 7 · 19163186 = 2 · 3 · 31
1415 = 3 · 56465 = 5 · 13114115 = 5 · 23164165 = 3 · 5 · 11
15341 = 11 · 3165112 = 2⁴ · 7115133 = 7 · 19165172 = 2² · 43
1651 = 3 · 176691 = 7 · 13116117 = 3² · 13166301 = 7 · 43
1745 = 3² · 56785 = 5 · 17117145 = 5 · 29167231 = 3 · 7 · 11
1825 = 5²6869 = 3 · 23118119 = 7 · 17168169 = 13²
1945 = 3² · 56985 = 5 · 17119177 = 3 · 59169231 = 3 · 7 · 11
2021 = 3 · 770169 = 13²120121 = 11²170171 = 3² · 19
2155 = 5 · 1171105 = 3 · 5 · 7121133 = 7 · 19171215 = 5 · 43
2269 = 3 · 237285 = 5 · 17122123 = 3 · 41172247 = 13 · 19
2333 = 3 · 1173111 = 3 · 37123217 = 7 · 31173205 = 5 · 41
2425 = 5²7475 = 3 · 5²124125 = 5³174175 = 5² · 7
2528 = 2² · 77591 = 7 · 13125133 = 7 · 19175319 = 11 · 19
2627 = 3³7677 = 7 · 11126247 = 13 · 19176177 = 3 · 59
2765 = 5 · 1377247 = 13 · 19127153 = 3² · 17177196 = 2² · 7²
2845 = 3² · 578341 = 11 · 31128129 = 3 · 43178247 = 13 · 19
2935 = 5 · 77991 = 7 · 13129217 = 7 · 31179185 = 5 · 37
3049 = 7²8081 = 3⁴130217 = 7 · 31180217 = 7 · 31
3149 = 7²8185 = 5 · 17131143 = 11 · 13181195 = 3 · 5 · 13
3233 = 3 · 118291 = 7 · 13132133 = 7 · 19182183 = 3 · 61
3385 = 5 · 1783105 = 3 · 5 · 7133145 = 5 · 29183221 = 13 · 17
3435 = 5 · 78485 = 5 · 17134135 = 3³ · 5184185 = 5 · 37
3551 = 3 · 1785129 = 3 · 43135221 = 13 · 17185217 = 7 · 31
3691 = 7 · 138687 = 3 · 29136265 = 5 · 53186187 = 11 · 17
3745 = 3² · 58791 = 7 · 13137148 = 2² · 37187217 = 7 · 31
3839 = 3 · 138891 = 7 · 13138259 = 7 · 37188189 = 3³ · 7
3995 = 5 · 198999 = 3² · 11139161 = 7 · 23189235 = 5 · 47
4091 = 7 · 139091 = 7 · 13140141 = 3 · 47190231 = 3 · 7 · 11
41105 = 3 · 5 · 791115 = 5 · 23141355 = 5 · 71191217 = 7 · 31
42205 = 5 · 419293 = 3 · 31142143 = 11 · 13192217 = 7 · 31
4377 = 7 · 1193301 = 7 · 43143213 = 3 · 71193276 = 2² · 3 · 23
4445 = 3² · 59495 = 5 · 19144145 = 5 · 29194195 = 3 · 5 · 13
4576 = 2² · 1995141 = 3 · 47145153 = 3² · 17195259 = 7 · 37
46133 = 7 · 1996133 = 7 · 19146147 = 3 · 7²196205 = 5 · 41
4765 = 5 · 1397105 = 3 · 5 · 7147169 = 13²197231 = 3 · 7 · 11
4849 = 7²9899 = 3² · 11148231 = 3 · 7 · 11198247 = 13 · 19
4966 = 2 · 3 · 1199145 = 5 · 29149175 = 5² · 7199225 = 3² · 5²
5051 = 3 · 17100153 = 3² · 17150169 = 13²200201 = 3 · 67

List of Fermat pseudoprimes in fixed base n

nFirst few Fermat pseudoprimes in base n OEIS 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) A002808
2341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... A001567
391, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... 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, ... A020136
54, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... 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, ... A005937
76, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... A020142
1514, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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, ... 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)

Bases b for which n is a Fermat pseudoprime

If composite is even, then is a Fermat pseudoprime to the trivial base . 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 [9] :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. [9] :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.

nbases 0 < b < n to which n is a Fermat pseudoprime# of bases
OEIS:  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, 9036
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, 13236
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 b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) (Table of pseudoprimes 16–4999). Unlike the list above, that page excludes the bases 1 and n−1. 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 a given n must divide (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 numbers which are pseudoprime to k 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 k is even and not totient of squarefree number, then the kth term of this sequence is 0.)

Weak pseudoprimes

A composite number n which satisfies is called a weak pseudoprime to base b. For any given base b, all Fermat pseudoprimes are weak pseudoprimes, and all weak pseudoprimes coprime to b are Fermat pseudoprimes. However, this definition also permits some pseudoprimes which are not coprime to b. [10] For example, the smallest even weak pseudoprime to base 2 is 161038 (see OEIS:  A006935 ).

The least weak pseudoprime to bases 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:  A000790

Carmichael numbers are weak pseudoprimes to all bases, thus all terms in this list are less than or equal to the smallest Carmichael number, 561. Except for 561 = 3⋅11⋅17, only semiprimes can occur in the above sequence. 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 ). The least Fermat pseudoprime to base b (also not necessary exceeding b) ( OEIS:  A090086 ) is usually semiprime, but not always; the first counterexample is A090086(648) = 385 = 5 × 7 × 11.

If we require n > b, the least weak pseudoprimes (for b = 1, 2, ...) are:

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:  A239293

Euler–Jacobi pseudoprimes

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.

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.

Related Research Articles

<span class="mw-page-title-main">Carmichael number</span> Composite number in number theory

In number theory, a Carmichael number is a composite number which in modular arithmetic satisfies the congruence relation:

In number theory, Fermat's little theorem states that if p is a prime number, then for any integer a, the number apa is an integer multiple of p. In the notation of modular arithmetic, this is expressed as

A super-Poulet number is a Poulet number, or pseudoprime to base 2, whose every divisor d divides

In mathematics, a Fermat number, named after Pierre de Fermat (1607–1665), the first known to have studied them, is a positive integer of the form: where n is a non-negative integer. The first few Fermat numbers are: 3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, ....

In number theory, an odd integer n is called an Euler–Jacobi probable prime to base a, if a and n are coprime, and

The Fermat primality test is a probabilistic test to determine whether a number is a probable prime.

In number theory, a probable prime (PRP) is an integer that satisfies a specific condition that is satisfied by all prime numbers, but which is not satisfied by most composite numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are composite, the condition is generally chosen in order to make such exceptions rare.

A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy. Some primality tests prove that a number is prime, while others like Miller–Rabin prove that a number is composite. Therefore, the latter might more accurately be called compositeness tests instead of primality tests.

The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

In mathematics, an odd composite integer n is called an Euler pseudoprime to base a, if a and n are coprime, and

300 is the natural number following 299 and preceding 301.

The Solovay–Strassen primality test, developed by Robert M. Solovay and Volker Strassen in 1977, is a probabilistic primality test to determine if a number is composite or probably prime. The idea behind the test was discovered by M. M. Artjuhov in 1967 (see Theorem E in the paper). This test has been largely superseded by the Baillie–PSW primality test and the Miller–Rabin primality test, but has great historical importance in showing the practical feasibility of the RSA cryptosystem. The Solovay–Strassen test is essentially an Euler–Jacobi probable prime test.

Lucas pseudoprimes and Fibonacci pseudoprimes are composite integers that pass certain tests which all primes and very few composite numbers pass: in this case, criteria relative to some Lucas sequence.

A strong pseudoprime is a composite number that passes the Miller–Rabin primality test. All prime numbers pass this test, but a small fraction of composites also pass, making them "pseudoprimes".

Multiplicative group of integers modulo <i>n</i> Group of units of the ring of integers modulo n

In modular arithmetic, the integers coprime to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n. Hence another name is the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. Here units refers to elements with a multiplicative inverse, which, in this ring, are exactly those coprime to n.

In mathematics, in particular number theory, an odd composite number N is a Somer–Lucas d-pseudoprime (with given d ≥ 1) if there exists a nondegenerate Lucas sequence with the discriminant such that and the rank appearance of N in the sequence U(PQ) is

In number theory, a Frobenius pseudoprime is a pseudoprime, whose definition was inspired by the quadratic Frobenius test described by Jon Grantham in a 1998 preprint and published in 2000. Frobenius pseudoprimes can be defined with respect to polynomials of degree at least 2, but they have been most extensively studied in the case of quadratic polynomials.

In mathematics, Pépin's test is a primality test, which can be used to determine whether a Fermat number is prime. It is a variant of Proth's test. The test is named after a French mathematician, Théophile Pépin.

The Baillie–PSW primality test is a probabilistic or possibly deterministic primality testing algorithm that determines whether a number is composite or is a probable prime. It is named after Robert Baillie, Carl Pomerance, John Selfridge, and Samuel Wagstaff.

<span class="mw-page-title-main">Perrin number</span> Number sequence 3,0,2,3,2,5,5,7,10,...

In mathematics, the Perrin numbers are a doubly infinite constant-recursive integer sequence with characteristic equation x3 = x + 1. The Perrin numbers bear the same relationship to the Padovan sequence as the Lucas numbers do to the Fibonacci sequence.

References

  1. 1 2 Samuel S. Wagstaff Jr. (2013). The Joy of Factoring. Providence, RI: American Mathematical Society. ISBN   978-1-4704-1048-3.
  2. 1 2 Desmedt, Yvo (2010). "Encryption Schemes". In Atallah, Mikhail J.; Blanton, Marina (eds.). Algorithms and theory of computation handbook: Special topics and techniques. CRC Press. pp. 10–23. ISBN   978-1-58488-820-8.
  3. Paulo Ribenboim (1996). The New Book of Prime Number Records. New York: Springer-Verlag. p. 108. ISBN   0-387-94457-5.
  4. Hamahata, Yoshinori; Kokubun, Y. (2007). "Cipolla Pseudoprimes" (PDF). Journal of Integer Sequences. 10 (8).
  5. 1 2 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 . Archived (PDF) from the original on 2005-03-04.
  6. Alford, W. R.; Granville, Andrew; Pomerance, Carl (1994). "There are Infinitely Many Carmichael Numbers" (PDF). Annals of Mathematics . 140 (3): 703–722. doi:10.2307/2118576. JSTOR   2118576. Archived (PDF) from the original on 2005-03-04.
  7. Kim, Su Hee; Pomerance, Carl (1989). "The Probability that a Random Probable Prime is Composite". Mathematics of Computation. 53 (188): 721–741. doi:10.2307/2008733. JSTOR   2008733.
  8. Sierpinski, W. (1988-02-15), "Chapter V.7", in Ed. A. Schinzel (ed.), Elementary Theory of Numbers, North-Holland Mathematical Library (2 Sub ed.), Amsterdam: North Holland, p. 232, ISBN   9780444866622
  9. 1 2 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. Archived (PDF) from the original on 2006-09-06.
  10. Michon, Gérard P. (19 November 2003). "Pseudo-primes, Weak Pseudoprimes, Strong Pseudoprimes, Primality". Numericana. Retrieved 21 April 2018.