Псевдопросто Ферма - Fermat pseudoprime

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

Определение

Маленькая теорема Ферма заявляет, что если п прост и а является совмещать к п, тогда а^п−1 - 1 это делимый от п. Для целого числа а > 1, если составное целое число Икс разделяет а^Икс−1 - 1, то Икс называется Псевдопросто Ферма основать а.^{[1]:Def. 3,32}Другими словами, составное целое число является псевдопервичным числом Ферма для основания а если он успешно пройдет Тест на простоту Ферма для базы а.^[2] Ложное утверждение о том, что все числа, прошедшие тест на простоту Ферма по основанию 2, простые, называется Китайская гипотеза.

Наименьшее псевдопростое число Ферма по основанию 2 равно 341. Это не простое число, поскольку оно равно 11 · 31, но удовлетворяет малой теореме Ферма: 2³⁴⁰ ≡ 1 (мод. 341) и, таким образом, проходитТест на простоту Ферма для базы 2.

Псевдопримеры по основанию 2 иногда называют Числа Сарруса, после П. Ф. Саррус кто обнаружил, что 341 обладает этим свойством, Номера пулетов, после П. Пуле кто составил таблицу таких чисел, или Ферматинцы (последовательность A001567 в OEIS ).

Псевдопростое число Ферма часто называют псевдопремия, с модификатором Ферма быть понятым.

Целое число Икс это псевдопростое число Ферма для всех значений а которые взаимно просты с Икс называется Число Кармайкла.^{[2][1]:Def. 3,34}

Свойства

Распределение

Для любой данной базы существует бесконечно много псевдопричин. а > 1. В 1904 году Чиполла показал, как создавать бесконечное количество псевдопреступников. а > 1: Пусть п быть простым числом, которое не делит а(а² - 1). Позволять А = (а^п - 1)/(а - 1) и пусть B = (а^п + 1)/(а + 1). потом п = AB является составным и является псевдопервичным основанием а.^[3] Например, если а = 2 и п = 5, тогда А = 31, B = 11 и п = 341 - псевдопростое число по основанию 2.

На самом деле их бесконечно много сильные псевдопреступности к любой базе больше 1 (см. теорему 1^[4]) и бесконечно много чисел Кармайкла,^[5] но они сравнительно редки. Есть три псевдопростых числа для основания 2 меньше 1000, 245 меньше одного миллиона и 21853 меньше 25 · 10.⁹. Имеется 4842 сильных псевдопростых числа с основанием 2 и 2163 числа Кармайкла ниже этого предела (см. Таблицу 1 ^[4]).

Начиная с 17 · 257, произведение последовательных чисел Ферма представляет собой псевдопростое число по основанию 2, как и все Композит Ферма и Композит Мерсенна.

Факторизации

Факторизации 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^d - 2 называется число супер-Пуле. Существует бесконечно много чисел Пуле, которые не являются числами суперпуле.^[6]

Наименьшие псевдопримеры Ферма

Наименьшее псевдопростое число для каждой базы а ≤ 200 приведено в следующей таблице; цвета отмечают количество простых множителей. В отличие от определения в начале статьи, псевдопределы ниже а исключены в таблице. (Для этого разрешить псевдопреступности ниже а, увидеть 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

Список псевдопримеров Ферма в фиксированной базе п

п	Первые несколько псевдопримеров Ферма в базе п	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, .. . (Все композиты)	A002808
2	341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911, ...	A001567
3	91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4961, 5551, 6601, 7381, 8401, 8911, ...	A005935
4	15, 85, 91, 341, 435, 451, 561, 645, 703, 1105, 1247, 1271, 1387, 1581, 1695, 1729, 1891, 1905, 2047, 2071, 2465, 2701, 2821, 3133, 3277, 3367, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5461, 5551, 6601, 6643, 7957, 8321, 8481, 8695, 8911, 9061, 9131, 9211, 9605, 9919, ...	A020136
5	4, 124, 217, 561, 781, 1541, 1729, 1891, 2821, 4123, 5461, 5611, 5662, 5731, 6601, 7449, 7813, 8029, 8911, 9881, ...	A005936
6	35, 185, 217, 301, 481, 1105, 1111, 1261, 1333, 1729, 2465, 2701, 2821, 3421, 3565, 3589, 3913, 4123, 4495, 5713, 6533, 6601, 8029, 8365, 8911, 9331, 9881, ...	A005937
7	6, 25, 325, 561, 703, 817, 1105, 1825, 2101, 2353, 2465, 3277, 4525, 4825, 6697, 8321, ...	A005938
8	9, 21, 45, 63, 65, 105, 117, 133, 153, 231, 273, 341, 481, 511, 561, 585, 645, 651, 861, 949, 1001, 1105, 1281, 1365, 1387, 1417, 1541, 1649, 1661, 1729, 1785, 1905, 2047, 2169, 2465, 2501, 2701, 2821, 3145, 3171, 3201, 3277, 3605, 3641, 4005, 4033, 4097, 4369, 4371, 4641, 4681, 4921, 5461, 5565, 5963, 6305, 6533, 6601, 6951, 7107, 7161, 7957, 8321, 8481, 8911, 9265, 9709, 9773, 9881, 9945, ...	A020137
9	4, 8, 28, 52, 91, 121, 205, 286, 364, 511, 532, 616, 671, 697, 703, 946, 949, 1036, 1105, 1288, 1387, 1541, 1729, 1891, 2465, 2501, 2665, 2701, 2806, 2821, 2926, 3052, 3281, 3367, 3751, 4376, 4636, 4961, 5356, 5551, 6364, 6601, 6643, 7081, 7381, 7913, 8401, 8695, 8744, 8866, 8911, ...	A020138
10	9, 33, 91, 99, 259, 451, 481, 561, 657, 703, 909, 1233, 1729, 2409, 2821, 2981, 3333, 3367, 4141, 4187, 4521, 5461, 6533, 6541, 6601, 7107, 7471, 7777, 8149, 8401, 8911, ...	A005939
11	10, 15, 70, 133, 190, 259, 305, 481, 645, 703, 793, 1105, 1330, 1729, 2047, 2257, 2465, 2821, 4577, 4921, 5041, 5185, 6601, 7869, 8113, 8170, 8695, 8911, 9730, ...	A020139
12	65, 91, 133, 143, 145, 247, 377, 385, 703, 1045, 1099, 1105, 1649, 1729, 1885, 1891, 2041, 2233, 2465, 2701, 2821, 2983, 3367, 3553, 5005, 5365, 5551, 5785, 6061, 6305, 6601, 8911, 9073, ...	A020140
13	4, 6, 12, 21, 85, 105, 231, 244, 276, 357, 427, 561, 1099, 1785, 1891, 2465, 2806, 3605, 5028, 5149, 5185, 5565, 6601, 7107, 8841, 8911, 9577, 9637, ...	A020141
14	15, 39, 65, 195, 481, 561, 781, 793, 841, 985, 1105, 1111, 1541, 1891, 2257, 2465, 2561, 2665, 2743, 3277, 5185, 5713, 6501, 6533, 6541, 7107, 7171, 7449, 7543, 7585, 8321, 9073, ...	A020142
15	14, 341, 742, 946, 1477, 1541, 1687, 1729, 1891, 1921, 2821, 3133, 3277, 4187, 6541, 6601, 7471, 8701, 8911, 9073, ...	A020143
16	15, 51, 85, 91, 255, 341, 435, 451, 561, 595, 645, 703, 1105, 1247, 1261, 1271, 1285, 1387, 1581, 1687, 1695, 1729, 1891, 1905, 2047, 2071, 2091, 2431, 2465, 2701, 2821, 3133, 3277, 3367, 3655, 3683, 4033, 4369, 4371, 4681, 4795, 4859, 5083, 5151, 5461, 5551, 6601, 6643, 7471, 7735, 7957, 8119, 8227, 8245, 8321, 8481, 8695, 8749, 8911, 9061, 9131, 9211, 9605, 9919, ...	A020144
17	4, 8, 9, 16, 45, 91, 145, 261, 781, 1111, 1228, 1305, 1729, 1885, 2149, 2821, 3991, 4005, 4033, 4187, 4912, 5365, 5662, 5833, 6601, 6697, 7171, 8481, 8911, ...	A020145
18	25, 49, 65, 85, 133, 221, 323, 325, 343, 425, 451, 637, 931, 1105, 1225, 1369, 1387, 1649, 1729, 1921, 2149, 2465, 2701, 2821, 2825, 2977, 3325, 4165, 4577, 4753, 5525, 5725, 5833, 5941, 6305, 6517, 6601, 7345, 8911, 9061, ...	A020146
19	6, 9, 15, 18, 45, 49, 153, 169, 343, 561, 637, 889, 905, 906, 1035, 1105, 1629, 1661, 1849, 1891, 2353, 2465, 2701, 2821, 2955, 3201, 4033, 4681, 5461, 5466, 5713, 6223, 6541, 6601, 6697, 7957, 8145, 8281, 8401, 8869, 9211, 9997, ...	A020147
20	21, 57, 133, 231, 399, 561, 671, 861, 889, 1281, 1653, 1729, 1891, 2059, 2413, 2501, 2761, 2821, 2947, 3059, 3201, 4047, 5271, 5461, 5473, 5713, 5833, 6601, 6817, 7999, 8421, 8911, ...	A020148
21	4, 10, 20, 55, 65, 85, 221, 703, 793, 1045, 1105, 1852, 2035, 2465, 3781, 4630, 5185, 5473, 5995, 6541, 7363, 8695, 8965, 9061, ...	A020149
22	21, 69, 91, 105, 161, 169, 345, 483, 485, 645, 805, 1105, 1183, 1247, 1261, 1541, 1649, 1729, 1891, 2037, 2041, 2047, 2413, 2465, 2737, 2821, 3241, 3605, 3801, 5551, 5565, 5963, 6019, 6601, 6693, 7081, 7107, 7267, 7665, 8119, 8365, 8421, 8911, 9453, ...	A020150
23	22, 33, 91, 154, 165, 169, 265, 341, 385, 451, 481, 553, 561, 638, 946, 1027, 1045, 1065, 1105, 1183, 1271, 1729, 1738, 1749, 2059, 2321, 2465, 2501, 2701, 2821, 2926, 3097, 3445, 4033, 4081, 4345, 4371, 4681, 5005, 5149, 6253, 6369, 6533, 6541, 7189, 7267, 7957, 8321, 8365, 8651, 8745, 8911, 8965, 9805, ...	A020151
24	25, 115, 175, 325, 553, 575, 805, 949, 1105, 1541, 1729, 1771, 1825, 1975, 2413, 2425, 2465, 2701, 2737, 2821, 2885, 3781, 4207, 4537, 6601, 6931, 6943, 7081, 7189, 7471, 7501, 7813, 8725, 8911, 9085, 9361, 9809, ...	A020152
25	4, 6, 8, 12, 24, 28, 39, 66, 91, 124, 217, 232, 276, 403, 426, 451, 532, 561, 616, 703, 781, 804, 868, 946, 1128, 1288, 1541, 1729, 1891, 2047, 2701, 2806, 2821, 2911, 2926, 3052, 3126, 3367, 3592, 3976, 4069, 4123, 4207, 4564, 4636, 4686, 5321, 5461, 5551, 5611, 5662, 5731, 5963, 6601, 7449, 7588, 7813, 8029, 8646, 8911, 9881, 9976, ...	A020153
26	9, 15, 25, 27, 45, 75, 133, 135, 153, 175, 217, 225, 259, 425, 475, 561, 589, 675, 703, 775, 925, 1035, 1065, 1147, 2465, 3145, 3325, 3385, 3565, 3825, 4123, 4525, 4741, 4921, 5041, 5425, 6093, 6475, 6525, 6601, 6697, 8029, 8695, 8911, 9073, ...	A020154
27	26, 65, 91, 121, 133, 247, 259, 286, 341, 365, 481, 671, 703, 949, 1001, 1105, 1541, 1649, 1729, 1891, 2071, 2465, 2665, 2701, 2821, 2981, 2993, 3146, 3281, 3367, 3605, 3751, 4033, 4745, 4921, 4961, 5299, 5461, 5551, 5611, 5621, 6305, 6533, 6601, 7381, 7585, 7957, 8227, 8321, 8401, 8911, 9139, 9709, 9809, 9841, 9881, 9919, ...	A020155
28	9, 27, 45, 87, 145, 261, 361, 529, 561, 703, 783, 785, 1105, 1305, 1413, 1431, 1885, 2041, 2413, 2465, 2871, 3201, 3277, 4553, 4699, 5149, 5181, 5365, 7065, 8149, 8321, 8401, 9841, ...	A020156
29	4, 14, 15, 21, 28, 35, 52, 91, 105, 231, 268, 341, 364, 469, 481, 561, 651, 793, 871, 1105, 1729, 1876, 1897, 2105, 2257, 2821, 3484, 3523, 4069, 4371, 4411, 5149, 5185, 5356, 5473, 5565, 5611, 6097, 6601, 7161, 7294, 8321, 8401, 8421, 8841, 8911, ...	A020157
30	49, 91, 133, 217, 247, 341, 403, 469, 493, 589, 637, 703, 871, 899, 901, 931, 1273, 1519, 1537, 1729, 2059, 2077, 2821, 3097, 3277, 3283, 3367, 3577, 4081, 4097, 4123, 5729, 6031, 6061, 6097, 6409, 6601, 6817, 7657, 8023, 8029, 8401, 8911, 9881, ...	A020158

Для получения дополнительной информации (от 31 до 100) см. OEIS: A020159 к OEIS: A020228, а для всех баз до 150 см. таблица псевдопримесей Ферма (текст на немецком языке), эта страница не определяет п является псевдопростом по отношению к основанию, конгруэнтному 1 или -1 (mod п)

Какие базы б сделать п псевдопремиум Ферма?

Если составной ${\displaystyle n}$ четно, тогда ${\displaystyle n}$ является псевдопервичным числом Ферма тривиальной базы ${\displaystyle b\equiv 1{\pmod {n}}}$.Если составной ${\displaystyle n}$ странно, то ${\displaystyle n}$ является псевдопервичным числом Ферма для тривиальных базисов ${\displaystyle b\equiv \pm 1{\pmod {n}}}$.

Для любого композита ${\displaystyle n}$, то количество различных баз ${\displaystyle b}$ по модулю ${\displaystyle n}$, для которого ${\displaystyle n}$ является основанием псевдопервика Ферма ${\displaystyle b}$, является^{[7]:Thm. 1, стр. 1392}

${\displaystyle \prod _{i=1}^{k}\gcd(p_{i}-1,n-1)}$

где ${\displaystyle p_{1},\dots ,p_{k}}$ различные простые множители ${\displaystyle n}$. Сюда входят тривиальные основы.

Например, для ${\displaystyle n=341=11\cdot 31}$, этот продукт ${\displaystyle \gcd(10,340)\cdot \gcd(30,340)=100}$. Для ${\displaystyle n=341}$, наименьшая такая нетривиальная база равна ${\displaystyle b=2}$.

Каждая нечетная композиция ${\displaystyle n}$ является псевдопервичным числом Ферма по крайней мере для двух нетривиальных базисов по модулю ${\displaystyle n}$ если только ${\displaystyle n}$ это степень 3.^{[7]:Кор. 1, стр. 1393}

Для композитного п <200, ниже приводится таблица всех оснований б < п который п - псевдопростое число Ферма. Если составное число п нет в таблице (или п находится в последовательности A209211 ), тогда п является псевдопервичным только для тривиальной базы 1 по модулю п.

п	базы б которому п является псевдопервичным числом Ферма (< п)	количество баз б (< п) (последовательность 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

За дополнительной информацией (п = От 201 до 5000), см.^[8] эта страница не определяет п является псевдопростом по отношению к основанию, конгруэнтному 1 или -1 (mod п). Когда п это простое число, п² псевдопростое число Ферма для б если и только если п это Виферих прайм основать б. Например, 1093² = 1194649 - псевдопростое число Ферма по основанию 2, а 11² = 121 - псевдопростое число Ферма по основанию 3.

Количество значений б для п являются (Для п простое число, количество значений б должно быть п - 1, так как все б удовлетворить Маленькая теорема Ферма )

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 )

Наименьшая база б > 1 который п является псевдопервичным основанием б (или простое число)

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 )

Количество значений б для п должен разделять ${\displaystyle \varphi }$ (п), или A000010 (п) = 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 частное может быть любым натуральным числом, а частное = 1 если и только если п это премьер или Число Кармайкла (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997 ), фактор = 2 тогда и только тогда, когда п находится в последовательности: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311 )

Наименьшее число с п ценности б есть (или 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 ) (если и только если п является даже и не тотент из бесквадратный номер, то п-й член этой последовательности равен 0)

Слабые псевдопремы

Составное число п которые удовлетворяют этому ${\displaystyle b^{n}\equiv b{\pmod {n}}}$ называется слабая псевдопервика к базе б. Этому условию удовлетворяет псевдопервичное число, лежащее в основе a (согласно обычному определению). И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростом в обычном смысле, иначе это может быть, а может и не быть.^[9] Наименее слабые псевдопробы для основания б = 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 (п ≤ q) меньше 561 встречается в приведенных выше последовательностях если и только если п - 1 делит q - 1. (см. OEIS: A108574) Кроме того, наименьшее псевдопростое число для основания п (также не обязательно превышение п) (OEIS: A090086) также обычно полупервично, первый контрпример A090086 (648) = 385 = 5 × 7 × 11.

Если нам потребуется п > б, они (для б = 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).

Псевдопримеры Эйлера – Якоби

Основная статья: Псевдопростое число Эйлера – Якоби

Другой подход - использовать более тонкие понятия псевдопримальности, например сильные псевдопреступности или Псевдопримеры Эйлера – Якоби, для которых нет аналогов Числа Кармайкла. Это ведет к вероятностные алгоритмы такой как Тест на простоту Соловея – Штрассена, то Тест на простоту Baillie-PSW, а Тест на простоту Миллера – Рабина, которые производят то, что известно как простые числа промышленного класса. Простые числа промышленного уровня - это целые числа, для которых первичность не была «сертифицирована» (т.е. строго доказана), но прошла тест, такой как тест Миллера – Рабина, который имеет ненулевую, но произвольно низкую вероятность неудачи.

Приложения

Редкость таких псевдопреступлений имеет важное практическое значение. Например, криптография с открытым ключом такие алгоритмы как ЮАР требуется умение быстро находить большие простые числа. Обычный алгоритм генерации простых чисел состоит в генерации случайных нечетных чисел и тестовое задание их для примитивности. Однако, детерминированный тесты на простоту проходят медленно. Если пользователь готов допустить сколь угодно малую вероятность того, что найденное число не является простым числом, а псевдопростом, можно использовать гораздо более быстрый и простой Тест на простоту Ферма.

использованная литература

1. Сэмюэл С. Вагстафф-мл. (2013). Радость факторинга. Провиденс, Род-Айленд: Американское математическое общество. ISBN  978-1-4704-1048-3.
2. Десмедт, Иво (2010). «Схемы шифрования». В Аталлах, Михаил Дж.; Блэнтон, Марина (ред.). Справочник по алгоритмам и теории вычислений: специальные темы и методы. CRC Press. С. 10–23. ISBN  978-1-58488-820-8.
3. Пауло Рибенбойм (1996). Новая книга рекордов простых чисел. Нью-Йорк: Springer-Verlag. п. 108. ISBN  0-387-94457-5.
4. Померанс, Карл; Селфридж, Джон Л.; Вагстафф, Сэмюэл С., мл. (Июль 1980 г.). «Псевдопреступности до 25 · 10⁹" (PDF). Математика вычислений. 35 (151): 1003–1026. Дои:10.1090 / S0025-5718-1980-0572872-7.
5. Олфорд, У.; Гранвиль, Эндрю; Померанс, Карл (1994). «Чисел Кармайкла бесконечно много» (PDF). Анналы математики. 140 (3): 703–722. Дои:10.2307/2118576. JSTOR  2118576.
6. Серпинский, В. (1988-02-15), "Глава V.7", в ред. А. Шинцель (ред.), Элементарная теория чисел, Математическая библиотека Северной Голландии (2-е изд.), Амстердам: Северная Голландия, стр. 232, ISBN  9780444866622
7. Роберт Бэйли; Сэмюэл С. Вагстафф мл. (Октябрь 1980 г.). "Лукас Псевдопримес" (PDF). Математика вычислений. 35 (152): 1391–1417. Дои:10.1090 / S0025-5718-1980-0583518-6. Г-Н  0583518.
8. "Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) - Wikibooks, Sammlung freier Lehr-, Sach- und Fachbücher". de.m.wikibooks.org. Получено 21 апреля 2018.
9. Мишон, Жерар. «Псевдопростые числа, Слабые псевдопредставления, Сильные псевдопредставления, Простое число - Numericana». www.numericana.com. Получено 21 апреля 2018.

внешние ссылки

• В. Ф. Голуэй и Ян Фейтсма, Таблицы псевдопреступлений для базы 2 и связанных данных (исчерпывающий список всех псевдопричин по основанию 2 ниже 2⁶⁴, включая факторизацию, сильные псевдопредставления и числа Кармайкла)
• Исследование псевдопремий