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

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

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


 Формально, нечётное составное число 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