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

Псевдопросты́е чи́сла Ферма́ — составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.

Определение

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

Составное число называется псевдопростым, если оно удовлетворяет некоторому необходимому (но не достаточному) условию простоты числа, то есть если оно обладает некоторыми свойствами простого числа.

Малая теорема Ферма

Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение $a^{n-1}\equiv 1{\pmod {n}}$ .

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

Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение $a^{n-1}\equiv 1{\pmod {n}}$ . Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a^[1]. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

Вариации

Существуют некоторые вариации определения:

Некоторые источники требуют, чтобы псевдопростое число было нечетным^[2], так как четное число очевидно является составным.
Каждое нечётное число $q$ удовлетворяет $a^{q-1}\equiv 1{\pmod {q}}$ для $a=q-1$ , поэтому в таком случае новой информации о числе $q$ мы не получим. Это исключается в определении, данном Крэндаллом и Померансом^[3]: Составное число $n$ является псевдопростым числом Ферма по основанию $a$ , если $a^{n-1}\equiv 1{\pmod {n}}$ и $2\leq a\leq n-2.$

Свойства

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

Существует бесконечно много псевдопростых чисел по данному основанию (более того существует бесконечно много сильных псевдопростых^[4] и бесконечно много чисел Кармайкла^[5]), но они довольно редки^[6]. Есть только три псевдопростых Ферма по основанию 2 меньше 1000, 245 меньше одного миллиона, и только 21 853 меньше, чем 25 миллиардов^[4].

Таблицы с некоторыми псевдопростыми числами Ферма

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

Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей^[7].

Наименьшие псевдопростые Ферма
a	Наименьшее п-пФ	a	Наименьшее п-пФ	a	Наименьшее п-пФ	a	Наименьшее п-пФ
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 · 13	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

Числа Пуле

Псевдопростые Ферма по основанию 2 называют числами Пуле, по имени бельгийского математика Пола Пуле^[англ.]^[8]. Разложение на множители шестидесяти первых чисел Пуле, в том числе тринадцати чисел Кармайкла (выделены жирным шрифтом), ниже в таблице.

Числа Пуле
Пуле 1 - 15		Пуле 16 - 30		Пуле 31 - 45		Пуле 46 - 60
341	11 · 31	4681	31 · 151	15709	23 · 683	33153	3 · 43 · 257
561	3 · 11 · 17	5461	43 · 127	15841	7 · 31 · 73	34945	5 · 29 · 241
645	3 · 5 · 43	6601	7 · 23 · 41	16705	5 · 13 · 257	35333	89 · 397
1105	5 · 13 · 17	7957	73 · 109	18705	3 · 5 · 29 · 43	39865	5 · 7 · 17 · 67
1387	19 · 73	8321	53 · 157	18721	97 · 193	41041	7 · 11 · 13 · 41
1729	7 · 13 · 19	8481	3 · 11 · 257	19951	71 · 281	41665	5 · 13 · 641
1905	3 · 5 · 127	8911	7 · 19 · 67	23001	3 · 11 · 17 · 41	42799	127 · 337
2047	23 · 89	10261	31 · 331	23377	97 · 241	46657	13 · 37 · 97
2465	5 · 17 · 29	10585	5 · 29 · 73	25761	3 · 31 · 277	49141	157 · 313
2701	37 · 73	11305	5 · 7 · 17 · 19	29341	13 · 37 · 61	49981	151 · 331
2821	7 · 13 · 31	12801	3 · 17 · 251	30121	7 · 13 · 331	52633	7 · 73 · 103
3277	29 · 113	13741	7 · 13 · 151	30889	17 · 23 · 79	55245	3 · 5 · 29 · 127
4033	37 · 109	13747	59 · 233	31417	89 · 353	57421	7 · 13 · 631
4369	17 · 257	13981	11 · 31 · 41	31609	73 · 433	60701	101 · 601
4371	3 · 31 · 47	14491	43 · 337	31621	103 · 307	60787	89 · 683

Число Пуле, все делители d которого делят также число 2^d − 2, называется суперчислом Пуле. Существует бесконечно много чисел Пуле, не являющихся суперчислами Пуле^[9].

Первые псевдопростые числа Ферма (до 10000) по основанию a

Первые псевдопростые числа Ферма (до 10000) по основанию a
a	Псевдопростые числа Ферма (до 10 000)	Последовательность 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 представлена в статьях A020159 — A020228 Энциклопедии целочисленных последовательностей^[10].

Основания, по которым число является псевдопростым

Ниже приведена таблица всех оснований b< n, для которых n — псевдопростое число Ферма (все составные числа являются псевдопростыми по основанию 1, а для b > n решение просто сдвигается на k * n, где k > 0), если составное число n не указано в таблице, то оно является псевдопростым только по основанию 1, или по основаниям, которые сравнимы с 1 (mod n), то есть число оснований b равно 1. Таблица составлена для n < 180^[11].

Основания b, по которым число n является псевдопростым
n	Основания b, для которых n является псевдопростым Ферма(< n)	Количество оснований b (< n)^[12]
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

Нужно отметить, что если p — простое, то p² есть псевдопростое Ферма по основанию b тогда и только тогда, когда p — простое число Вифериха по основанию b. Например, 1093² = 1 194 649 — псевдопростое Ферма по основанию 2.

Количество оснований 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 — псевдопростое (или простое):

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).

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

Составное число n, для которого справедливо сравнение bⁿ = b (mod n), называется слабым псевдопростым числом Ферма по основанию b (здесь b не обязано быть взаимно простым с n)^[13]. Наименьшие слабые псевдопростые по основанию b:

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)

Если требуется, чтобы n > b, тогда:

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)

Приложения

Благодаря своей редкости, такие псевдопростые числа имеют важные практические применения. Например, для криптографических алгоритмов с открытым ключом, таких как RSA, требуется возможность быстро находить большие простые числа^[14]. Обычный алгоритм для генерации простых чисел должен генерировать случайные нечётные числа и проверять их на простоту. Тем не менее детерминированные тесты простоты работают медленно. Если мы готовы допустить сколь угодно малую вероятность того, что найденное число не простое, но псевдопростое, можно использовать гораздо более быстрый и простой тест Ферма.

Примечания

↑ Desmedt, Yvo. Encryption Schemes // Algorithms and theory of computation handbook: Special topics and techniques (англ.) / Atallah, Mikhail J.^[англ.] & Blanton, Marina. — CRC Press, 2010. — P. 10—23. — ISBN 978-1-58488-820-8.
↑ Weisstein, Eric W. Fermat Pseudoprime (англ.) на сайте Wolfram MathWorld.
↑ Крэндалл, Померанс, 2011, с. 155.
↑ ¹ ² Померанс, Селфридж, Вагстафф, 1980, Теорема 1.
↑ W. R. Alford^[англ.]; Andrew Granville; Carl Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 марта 2005 года.
↑ Крэндалл, Померанс, 2011, Теорема 3.4.2, с. 154-155.
↑ последовательность A007535 в OEIS
↑ последовательность A001567 в OEIS
↑ W. Sierpinski. Chapter V.7 // Elementary Theory of Numbers = Teoria Liczb / Ed. A. Schinzel. — 2 Sub edition. — Amsterdam: North Holland, 1988-02-15. — С. 232. — 528 с. — (North-Holland Mathematical Library). — ISBN 9780444866622. Архивировано 8 декабря 2015 года.
↑ См. также таблицу псевдопростых чисел Ферма для оснований до 150 (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).
↑ Более подробная информация для n = 181…5000 есть в таблице (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).
↑ последовательность A063994 в OEIS
↑ Крэндалл, Померанс, 2011, Теорема 3.4.1, с. 154.
↑ Крэндалл, Померанс, 2011, Алгоритм 8.1.2, с. 438.

Литература

Ричард Крэндалл, Карл Померанс. Простые числа: Криптографические и вычислительные аспекты. — Книжный дом "ЛИБРОКОМ", 2011. — P. 154—158, 438—441.
Carl Pomerance; John L. Selfridge^[англ.], Samuel S. Wagstaff, Jr^[англ.]. The pseudoprimes to 25·10⁹ (англ.) // Mathematics of Computation^[англ.] : journal. — 1980. — July (vol. 35, no. 151). — P. 1003—1026. — doi:10.1090/S0025-5718-1980-0572872-7.

[desmedt-10-23-1] Desmedt, Yvo. Encryption Schemes // Algorithms and theory of computation handbook: Special topics and techniques (англ.) / Atallah, Mikhail J.^[англ.] & Blanton, Marina. — CRC Press, 2010. — P. 10—23. — ISBN 978-1-58488-820-8.

[2] Weisstein, Eric W. Fermat Pseudoprime (англ.) на сайте Wolfram MathWorld.

[_08c79d7fbb134626-3] Крэндалл, Померанс, 2011, с. 155.

[_2cd08c4b7f118374-4] ¹ ² Померанс, Селфридж, Вагстафф, 1980, Теорема 1.

[Alford1994-5] W. R. Alford^[англ.]; Andrew Granville; Carl Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 марта 2005 года.

[_85ad37b0da0694a9-6] Крэндалл, Померанс, 2011, Теорема 3.4.2, с. 154-155.

[7] последовательность A007535 в OEIS

[8] последовательность A001567 в OEIS

[9] W. Sierpinski. Chapter V.7 // Elementary Theory of Numbers = Teoria Liczb / Ed. A. Schinzel. — 2 Sub edition. — Amsterdam: North Holland, 1988-02-15. — С. 232. — 528 с. — (North-Holland Mathematical Library). — ISBN 9780444866622. Архивировано 8 декабря 2015 года.

[10] См. также таблицу псевдопростых чисел Ферма для оснований до 150 (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).

[11] Более подробная информация для n = 181…5000 есть в таблице (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).

[12] последовательность A063994 в OEIS

[_8aa375f8a4799b66-13] Крэндалл, Померанс, 2011, Теорема 3.4.1, с. 154.

[_837f6aa8eea7ad2f-14] Крэндалл, Померанс, 2011, Алгоритм 8.1.2, с. 438.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

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

Содержание

Определение