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

 Вероятно простое число — это число, которое проходит тест простоты.Сильное вероятно простое число — это число, которое проходитсильную версию теста простоты. Сильное псевдопростоечисло — это составное число, которое проходит сильную версиютеста простоты.
 Все простые числа проходят этот тест, но небольшая доля составных чиселтакже этот тест проходит, что делает их «ложно простыми».
 В отличие от псевдопростых чисел Ферма, для которых существуют числа,псевдопростые по всем взаимно простым основаниям (числа Кармайкла), несуществует составных чисел, сильных псевдопростых по всем основаниям.

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


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

ad1modn
 или

ad2r1modn для некоторого 0r<s.
 (Если число n удовлетворяет вышеприведённым условиям и мы незнаем, простое оно или нет, более точно называть его сильным вероятнопростым по основанию a. Если же мы знаем, что 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, ... .
 По основанию 3

 121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345,23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913,88573, 97567, ... .
 По основанию 5

 781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539,38081, 40501, 44801, 53971, 79381, ... .
 По основанию 4 см. , а по основаниям от 6 до 100 см. последовательностиот до .
 Если проверять вышеприведённые условия по нескольким основаниям,получаем более мощный тест на простоту, чем при использовании теста поодному основанию. Например, существует только 13 чисел, меньших25•109, являющихся сильными псевдопростыми пооснованиям 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 является простым.
 При осторожном выборе основания, не являющегося простым, можно построитьдаже лучшие тесты. Например, не существует составных чисел <264,сильных псевдопростых по всем семи основаниям 2, 325, 9375, 28178,450775, 9780504 и 1795265022.

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


nНаименьшееnНаименьшееnНаименьшееnНаименьшее
193354565339749
2204734336665989
312135967339925
4341363568251009
5781379693510125
621738397069102133
7253913371910351
894039728510415
9914121739105451
10942451741510615
11133432175911079
1291449761510891
13854548177391099
14154697877110111
1516874765793911155
1615484980911265
1794925819111357
18255049829114115
1995125832111557
2021525184851169
21221539852111749
2221545586851189
231695598724711915
24255655888712091
25217572589912115
2695857909112265
27121591591912385
28960481929112425
2915611593251259
3049629949312625
3115635299518911279
3225649969512849