Псевдопростые числа Ферма
В теории чисел псевдопростые числа Ферма составляют наиболее важный класс псевдопростых чисел , возникший из малой теоремы Ферма .
Определение [ править ]
Маленькая теорема Ферма утверждает, что если p простое и a взаимно просто с p , то a р -1 − 1 делится на p . Для положительного целого числа a , если составное целое число x делит a х -1 − 1, то x называется псевдопростым числом Ферма по основанию a . [1] : Определен. 3.32 Другими словами, составное целое число является псевдопростым числом Ферма по основанию a, если оно успешно проходит тест на простоту Ферма по основанию a . [2] Ложное утверждение о том, что все числа, которые проходят тест на простоту Ферма по основанию 2, являются простыми, называется китайской гипотезой .
Наименьшее псевдопростое число Ферма по основанию 2 — 341. Это не простое число, поскольку оно равно 11 · 31, но оно удовлетворяет малой теореме Ферма: 2 340 ≡ 1 (по модулю 341) и, таким образом, проходит Тест Ферма на простоту по основанию 2.
Псевдопростые числа по основанию 2 иногда называют числами Сарруса , в честь П. Ф. Сарруса, обнаружившего, что 341 обладает этим свойством, числами Пуле , в честь П. Пуле, составившего таблицу таких чисел, или ферматианами (последовательность A001567 в OEIS ).
Псевдопростое число Ферма часто называют псевдопростым , имея в виду модификатор Ферма .
Целое число x , которое является псевдопростым числом Ферма для всех значений a , взаимно простых с x, называется числом Кармайкла . [2] [1] : Определен. 3.34
Свойства [ править ]
Распространение [ править ]
Существует бесконечно много псевдопростых чисел по любому основанию a > 1. В 1904 году Чиполла показал, как получить бесконечное количество псевдопростых чисел по основанию a > 1: пусть A = ( a п - 1)/( a - 1) и пусть B = ( a п + 1)/( a + 1), где p — простое число, не делящее a ( a 2 - 1). Тогда n = AB составное число и псевдопростое число по основанию a . [3] [4] Например, если a = 2 и p = 5, то A = 31, B = 11 и n = 341 — псевдопростое число по основанию 2.
В действительности существует бесконечно много сильных псевдопростых чисел по любому основанию больше 1 (см. теорему 1 [5] ) и бесконечно много чисел Кармайкла, [6] но они сравнительно редки. Существует три псевдопростых числа с основанием 2 ниже 1000, 245 ниже миллиона и 21853 меньше 25·10. 9 . Ниже этого предела имеется 4842 сильных псевдопростых числа по основанию 2 и 2163 числа Кармайкла (см. Таблицу 1). [5] ).
Начиная с 17·257, произведение последовательных чисел Ферма является псевдопростым числом по основанию 2, как и все композиты Ферма и композиты Мерсенна .
Вероятность того, что составное число n пройдет тест Ферма, приближается к нулю для . В частности, Ким и Померанс показали следующее: Вероятность того, что случайное нечетное число n ≤ x является псевдопростым числом Ферма по случайному основанию. меньше 2,77·10 -8 для х= 10 100 , и не более (log x) -197 <10 -10,000 для x≥10 100,000 . [7]
Факторизации [ править ]
Факторизация 60 чисел Пуле до 60787, включая 13 чисел Кармайкла (выделены жирным шрифтом), представлена в следующей таблице.
(последовательность A001567 в OEIS )
|
|
|
|
Число Пуле, все делители которого d делят 2. д − 2 называется суперчислом Пуле . Существует бесконечно много чисел Пуле, которые не являются суперчислами Пуле. [8]
псевдопростые Ферма числа Наименьшие
Наименьшее псевдопростое число для каждого основания a ≤ 200 указано в следующей таблице; цвета обозначают количество простых множителей. В отличие от определения в начале статьи, псевдопростые числа ниже a в таблице исключены . (Чтобы разрешить псевдопростые числа ниже a , см. OEIS : A090086 ).
(последовательность A007535 в OEIS )
а | наименьший пп | а | наименьший пп | а | наименьший пп | а | наименьший пп |
---|---|---|---|---|---|---|---|
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 |
Список псевдопростых чисел Ферма с фиксированной базой n [ править ]
н | Первые несколько псевдопростых чисел Ферма по основанию n | OEIS Последовательность |
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,.. . (Все композиты) | А002808 |
2 | 341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ... | А001567 |
3 | 91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ... | А005935 |
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, ... | А020136 |
5 | 4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ... | А005936 |
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, ... | А005937 |
7 | 6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ... | А005938 |
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, ... | А020137 |
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, ... | А020138 |
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, ... | А005939 |
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, ... | А020139 |
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, ... | А020140 |
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, ... | А020141 |
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, ... | А020142 |
15 | 14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ... | А020143 |
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, ... | А020144 |
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, ... | А020145 |
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, ... | А020146 |
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, ... | А020147 |
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, ... | А020148 |
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, ... | А020149 |
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, ... | А020150 |
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, ... | А020151 |
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, ... | А020152 |
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, ... | А020153 |
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, ... | А020154 |
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, ... | А020155 |
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, ... | А020156 |
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, ... | А020157 |
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, ... | А020158 |
Для получения дополнительной информации (по основанию от 31 до 100) см. OEIS : от A020159 до OEIS : A020228 , а для всех оснований до 150 см. таблицу псевдопростых чисел Ферма (текст на немецком языке) , на этой странице не определено, что n является псевдопростым числом по основанию. конгруэнтно 1 или -1 (по модулю n )
Какие основания b делают n псевдопростым числом Ферма? [ редактировать ]
Если составной четно, тогда является псевдопростым числом Ферма тривиальной базы .Если составной странно, тогда является псевдопростым числом Ферма относительно тривиальных базисов .
Для любого композита , количество различных оснований модуль , для чего является псевдопростым основанием Ферма , является [9] : Тэм. 1, с. 1392
где являются отдельными простыми факторами . Сюда входят тривиальные основания.
Например, для , этот продукт . Для , наименьшая такая нетривиальная база равна .
Каждый нечетный состав является псевдопростым числом Ферма по крайней мере для двух нетривиальных базисов по модулю пока не это степень 3. [9] : Кор. 1, с. 1393
Для составного n < 200 ниже представлена таблица всех оснований b < n , где n является псевдопростым числом Ферма. Если составного числа n нет в таблице (или n находится в последовательности A209211 ), то n является псевдопростым только по тривиальному основанию 1 по модулю n .
н | базисы b , для которых n является псевдопростым числом Ферма (< n ) | количество оснований b (< n ) (последовательность A063994 в 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 |
Дополнительную информацию ( n = от 201 до 5000) см. [10] на этой странице не определено, что n является псевдопростым числом по основанию, конгруэнтному 1 или -1 (по модулю n ). Когда p — простое число, p 2 является псевдопростым числом Ферма по основанию b тогда и только тогда, когда p является простым числом Вифериха по основанию b . Например, 1093 2 = 1194649 является псевдопростым числом Ферма по основанию 2, а 11 2 = 121 является псевдопростым числом Ферма по основанию 3.
Число значений b для n равно (Для n простого числа число значений b должно быть n - 1, поскольку все b удовлетворяют малой теореме Ферма )
- 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, ... (последовательность A063994 в OEIS )
Наименьшее основание b > 1, при котором n является псевдопростым числом по основанию b (или простому числу), равно
- 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, ... (последовательность A105222 в OEIS )
Число значений b для n должно делиться ( n ) или 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, ... ( Частное может быть любым натуральным числом, и частное = 1 тогда и только тогда, когда n является простым числом или числом Кармайкла (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997 ), частное = 2 тогда и только тогда, когда n находится в последовательности: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... А191311 )
Наименьшее число с n значениями b равно (или 0, если такого числа не существует)
- 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, ... (последовательность A064234 в OEIS ) ( тогда и только если n четное бесквадратному и не равно числу , тогда n- й член этой последовательности равен 0)
Слабые псевдопростые числа [ править ]
Составное число n, удовлетворяющее этому называется слабым псевдопростым по основанию b . Псевдопростое число по основанию a (по обычному определению) удовлетворяет этому условию. И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростым в обычном смысле, в противном случае это может быть так, а может и не быть. [11] Наименее слабые псевдопростые числа по основанию b = 1, 2,...:
- 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, ... (последовательность A000790 в OEIS )
Все члены меньше или равны наименьшему числу Кармайкла, 561. За исключением 561, в приведенной выше последовательности могут встречаться только полупростые числа , но не все полупростые числа меньше 561 встречаются, полупростые числа pq ( p ≤ q ) меньше 561 встречаются в вышеуказанные последовательности тогда и только тогда, когда p - 1 делит q - 1. (см. OEIS : A108574 ). Кроме того, наименьшее псевдопростое число по основанию n (также не обязательно превосходящее n ) ( OEIS : A090086 ) также обычно является полупростым, первый контрпример: А090086 (648)=385=5×7×11.
Если нам потребуется n > b , они будут (для 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, ... (последовательность A239293 в OEIS )
Числа Кармайкла являются слабыми псевдопростыми числами по всем основаниям.
Наименьшее даже слабое псевдопростое число по основанию 2 — 161038 (см. OEIS : A006935 ).
Эйлера– Якоби числа Псевдопростые
Другой подход состоит в использовании более тонких понятий псевдопростых чисел, например, сильных псевдопростых чисел или псевдопростых чисел Эйлера-Якоби , для которых нет аналогов чисел Кармайкла . Это приводит к появлению вероятностных алгоритмов, таких как тест простоты Соловея-Штрассена , тест простоты Бэйли-ПСВ и тест простоты Миллера-Рабина , которые создают так называемые простые числа промышленного уровня . Простые числа промышленного уровня - это целые числа, простота которых не была «сертифицирована» (т.е. строго доказана), но прошла такой тест, как тест Миллера-Рабина, который имеет ненулевую, но сколь угодно низкую вероятность отказа.
Приложения [ править ]
Редкость таких псевдопростых чисел имеет важные практические последствия. Например, алгоритмы криптографии с открытым ключом, такие как RSA, требуют способности быстро находить большие простые числа. Обычный алгоритм генерации простых чисел заключается в генерации случайных нечетных чисел и проверке их на простоту. Однако детерминированные тесты на простоту выполняются медленно. Если пользователь готов допустить сколь угодно малую вероятность того, что найденное число является не простым, а псевдопростым, можно использовать гораздо более быстрый и простой тест на простоту Ферма .
Ссылки [ править ]
- ^ Jump up to: а б Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. ISBN 978-1-4704-1048-3 .
- ^ Jump up to: а б Десмедт, Иво (2010). «Схемы шифрования» . В Аталле Михаил Дж .; Блэнтон, Марина (ред.). Справочник по алгоритмам и теории вычислений: Специальные темы и методы . ЦРК Пресс. стр. 10–23. ISBN 978-1-58488-820-8 .
- ^ Пауло Рибенбойм (1996). Новая книга рекордов простых чисел . Нью-Йорк: Springer-Verlag . п. 108. ИСБН 0-387-94457-5 .
- ^ Хамахата, Ёсинори; Кокубун, Ю. (2007). «Псевдопростые числа Чиполлы» (PDF) . Журнал целочисленных последовательностей . 10 (8).
- ^ Jump up to: а б Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С. младший (июль 1980 г.). «Псевдопростые числа до 25·10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . Архивировано (PDF) из оригинала 4 марта 2005 г.
- ^ Алфорд, WR ; Гранвилл, Эндрю ; Померанс, Карл (1994). «Чисел Кармайкла бесконечно много» (PDF) . Анналы математики . 140 (3): 703–722. дои : 10.2307/2118576 . JSTOR 2118576 . Архивировано (PDF) из оригинала 4 марта 2005 г.
- ^ Ким, Су Хи; Померанс, Карл (1989). «Вероятность того, что случайное вероятное простое число является составным» . Математика вычислений . 53 (188): 721–741. дои : 10.2307/2008733 . JSTOR 2008733 .
- ^ Серпинский, В. (15 февраля 1988 г.), «Глава V.7», в ред. А. Шинцель (редактор), Элементарная теория чисел , Математическая библиотека Северной Голландии (2 подред.), Амстердам: Северная Голландия, стр. 232, ISBN 9780444866622
- ^ Jump up to: а б Роберт Бэйли; Сэмюэл С. Вагстафф младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . МР 0583518 . Архивировано (PDF) из оригинала 6 сентября 2006 г.
- ^ «Псевдопростые числа: Таблица псевдопростых чисел (15 — 4999) — Викибуки, сборник бесплатных учебников, научно-популярной и специальной литературы» . de.m.wikibooks.org . Проверено 21 апреля 2018 г.
- ^ Мишон, Жерар. «Псевдопростые числа, Слабые псевдопростые числа, Сильные псевдопростые числа, Простота — Нумерикана» . www.numericana.com . Проверено 21 апреля 2018 г.
Внешние ссылки [ править ]
- В. Ф. Голуэй и Ян Фейтсма, Таблицы псевдопростых чисел по основанию 2 и связанные с ними данные (полный список всех псевдопростых чисел по основанию 2 ниже 2) 64 , включая факторизацию, сильные псевдопростые числа и числа Кармайкла)
- Исследование псевдопростых чисел