Сильное псевдопростое число

Вероятно простое число — это число, которое проходит тест простоты. Сильное вероятно простое число — это число, которое проходит сильную версию теста простоты. Сильное псевдопростое число — это составное число, которое проходит сильную версию теста простоты.

Все простые числа проходят этот тест, но небольшая доля составных чисел также этот тест проходит, что делает их «ложно простыми».

В отличие от псевдопростых чисел Ферма, для которых существуют числа, псевдопростые по всем взаимно простым основаниям (числа Кармайкла), не существует составных чисел, сильных псевдопростых по всем основаниям.

Формальное определение

Формально, нечётное составное число n = d • 2^s + 1 с нечётным d называется сильным псевдопростым числом (Ферма) по основанию a, если выполняется одно из условий:

$a^{d}\equiv 1{\pmod {n}}$

или

$a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}$ для некоторого $0\leq r<s.$

(Если число n удовлетворяет вышеприведённым условиям и мы не знаем, простое оно или нет, более точно называть его сильным вероятно простым по основанию a. Если же мы знаем, что n не простое, можно употреблять термин сильное псевдопростое число.)

Определение тривиально выполняется, если a ≡ ±1 mod n, так что эти тривиальные случаи часто исключаются.

Ричард Гай ошибочно дал определение только с первым условием, но ему удовлетворяют не все простые числа.

Свойства сильных псевдопростых чисел

Сильное псевдопростое число по основанию a всегда является псевдопростым Эйлера — Якоби, псевдопростым Эйлера и псевдопростым Ферма по этому основанию, но не все псевдопростые Эйлера и Ферма являются сильными псевдопростыми. Числа Кармайкла могут быть сильными псевдопростыми по некоторым основаниям, например, 561 является сильными псевдопростым по основанию 50, но не по всем базисам.

Составное число n является сильным псевдопростым максимум четверти всех оснований, меньших n . Таким образом, нет «сильных чисел Кармайкла», чисел, которые являются сильными псевдопростыми для всех оснований. Следовательно, если задано случайное основание, вероятность, что число будет сильным псевдопростым по этому основанию, не превосходит 1/4, что используется в широко распространённом тесте Миллера — Рабина. Тем не менее, Арно привёл 397-значное составное число, являющееся сильным псевдопростым по любому основанию, меньшему 307. Один из способов уберечься от объявления таких чисел вероятно простыми заключается в комбинации теста на сильное возможно простое число с тестом на псевдопростое число Люка, как в тесте Бейли — Померанца — Селфриджа — Уогстаффа.

Существует бесконечно много сильных псевдопростых по любому конкретному основанию.

Примеры

Первые сильные псевдопростые по основанию 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, ... (последовательность A001262 в OEIS).

По основанию 3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, ... (последовательность A020229 в OEIS).

По основанию 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, ... (последовательность A020231 в OEIS).

По основанию 4 см. A020230, а по основаниям от 6 до 100 см. последовательности от A020232 до A020326.

Если проверять вышеприведённые условия по нескольким основаниям, получаем более мощный тест на простоту, чем при использовании теста по одному основанию. Например, существует только 13 чисел, меньших 25•10⁹, являющихся сильными псевдопростыми по основаниям 2, 3 и 5 одновременно. Они перечислены в таблице 7 в статье Померанса и Селфриджа. Наименьшее такое число — 25326001. Это означает, что при n меньшем 25326001, если n является сильным возможно простым число по основаниям 2, 3 и 5, число n является простым.

Число 3825123056546413051 является наименьшим числом, одновременно являющимся сильным псевдопростым по 9 основаниям 2, 3, 5, 7, 11, 13, 17, 19 и 23 . Так что при n меньшем 3825123056546413051, если n является сильным вероятно простым по этим 9 основаниям, то n является простым.

При осторожном выборе основания, не являющегося простым, можно построить даже лучшие тесты. Например, не существует составных чисел $<2^{64}$, сильных псевдопростых по всем семи основаниям 2, 325, 9375, 28178, 450775, 9780504 и 1795265022.

Наименьшее сильное псевдопростое по основанию n

n	Наименьшее	n	Наименьшее	n	Наименьшее	n	Наименьшее
1	9	33	545	65	33	97	49
2	2047	34	33	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	781	37	9	69	35	101	25
6	217	38	39	70	69	102	133
7	25	39	133	71	9	103	51
8	9	40	39	72	85	104	15
9	91	41	21	73	9	105	451
10	9	42	451	74	15	106	15
11	133	43	21	75	91	107	9
12	91	44	9	76	15	108	91
13	85	45	481	77	39	109	9
14	15	46	9	78	77	110	111
15	1687	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	57
18	25	50	49	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	221	53	9	85	21	117	49
22	21	54	55	86	85	118	9
23	169	55	9	87	247	119	15
24	25	56	55	88	87	120	91
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	65
27	121	59	15	91	9	123	85
28	9	60	481	92	91	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	93	126	25
31	15	63	529	95	1891	127	9
32	25	64	9	96	95	128	49