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

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

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

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

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

Примечания

Литература