Jump to content

Псевдопростые числа Ферма

В теории чисел псевдопростые числа Ферма составляют наиболее важный класс псевдопростых чисел , возникший из малой теоремы Ферма .

Определение [ править ]

Маленькая теорема Ферма утверждает, что если 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 )

Курица от 1 до 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
Курица с 16 до 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
Курица от 31 до 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
Курица 46 на 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

Число Пуле, все делители которого 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, требуют способности быстро находить большие простые числа. Обычный алгоритм генерации простых чисел заключается в генерации случайных нечетных чисел и проверке их на простоту. Однако детерминированные тесты на простоту выполняются медленно. Если пользователь готов допустить сколь угодно малую вероятность того, что найденное число является не простым, а псевдопростым, можно использовать гораздо более быстрый и простой тест на простоту Ферма .

Ссылки [ править ]

  1. ^ Jump up to: а б Сэмюэл С. Вагстафф младший (2013). Радость факторинга . Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-1-4704-1048-3 .
  2. ^ Jump up to: а б Десмедт, Иво (2010). «Схемы шифрования» . В Аталле Михаил Дж .; Блэнтон, Марина (ред.). Справочник по алгоритмам и теории вычислений: Специальные темы и методы . ЦРК Пресс. стр. 10–23. ISBN  978-1-58488-820-8 .
  3. ^ Пауло Рибенбойм (1996). Новая книга рекордов простых чисел . Нью-Йорк: Springer-Verlag . п. 108. ИСБН  0-387-94457-5 .
  4. ^ Хамахата, Ёсинори; Кокубун, Ю. (2007). «Псевдопростые числа Чиполлы» (PDF) . Журнал целочисленных последовательностей . 10 (8).
  5. ^ Jump up to: а б Померанс, Карл ; Селфридж, Джон Л .; Вагстафф, Сэмюэл С. младший (июль 1980 г.). «Псевдопростые числа до 25·10 9 » (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . Архивировано (PDF) из оригинала 4 марта 2005 г.
  6. ^ Алфорд, WR ; Гранвилл, Эндрю ; Померанс, Карл (1994). «Чисел Кармайкла бесконечно много» (PDF) . Анналы математики . 140 (3): 703–722. дои : 10.2307/2118576 . JSTOR   2118576 . Архивировано (PDF) из оригинала 4 марта 2005 г.
  7. ^ Ким, Су Хи; Померанс, Карл (1989). «Вероятность того, что случайное вероятное простое число является составным» . Математика вычислений . 53 (188): 721–741. дои : 10.2307/2008733 . JSTOR   2008733 .
  8. ^ Серпинский, В. (15 февраля 1988 г.), «Глава V.7», в ред. А. Шинцель (редактор), Элементарная теория чисел , Математическая библиотека Северной Голландии (2 подред.), Амстердам: Северная Голландия, стр. 232, ISBN  9780444866622
  9. ^ Jump up to: а б Роберт Бэйли; Сэмюэл С. Вагстафф младший (октябрь 1980 г.). «Лукас Псевдопраймс» (PDF) . Математика вычислений . 35 (152): 1391–1417. дои : 10.1090/S0025-5718-1980-0583518-6 . МР   0583518 . Архивировано (PDF) из оригинала 6 сентября 2006 г.
  10. ^ «Псевдопростые числа: Таблица псевдопростых чисел (15 — 4999) — Викибуки, сборник бесплатных учебников, научно-популярной и специальной литературы» . de.m.wikibooks.org . Проверено 21 апреля 2018 г.
  11. ^ Мишон, Жерар. «Псевдопростые числа, Слабые псевдопростые числа, Сильные псевдопростые числа, Простота — Нумерикана» . www.numericana.com . Проверено 21 апреля 2018 г.

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 34c0347b91ec7020447a3d12af605b89__1712773500
URL1:https://arc.ask3.ru/arc/aa/34/89/34c0347b91ec7020447a3d12af605b89.html
Заголовок, (Title) документа по адресу, URL1:
Fermat pseudoprime - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)