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

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

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

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

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

${\displaystyle a^{d}\equiv 1\mod n}$

или

${\displaystyle a^{d\cdot 2^{r}}\equiv -1\mod n}$ для некоторого ${\displaystyle 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, ... (последовательность в 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, ... (последовательность в OEIS ).

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

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

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

Если проверять вышеприведённые условия по нескольким основаниям, получаем более мощный тест на простоту, чем при использовании теста по одному основанию. Например, существует только 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 является простым.

При осторожном выборе основания, не являющегося простым, можно построить даже лучшие тесты. Например, не существует составных чисел ${\displaystyle <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

Примечания

Литература