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

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

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

Мотивация и первые примеры [ править ]

Допустим, мы хотим выяснить, является ли n = 31697 вероятным простым числом (PRP). Выберем основание a = 3 и, вдохновившись маленькой теоремой Ферма , вычислим:

${\ displaystyle 3 ^ {31696} \ Equiv 1 {\ pmod {31697}}}$

Это показывает, что 31697 - это PRP Ферма (база 3), поэтому мы можем подозревать, что это простое число. Теперь мы несколько раз уменьшаем показатель вдвое:

${\ displaystyle 3 ^ {15848} \ Equiv 1 {\ pmod {31697}}}$

${\displaystyle 3^{7924}\equiv 1{\pmod {31697}}}$

${\displaystyle 3^{3962}\equiv 28419{\pmod {31697}}}$

Первые несколько раз не дали ничего интересного (результат все еще был 1 по модулю 31697), но при экспоненте 3962 мы видим результат, который не равен ни 1, ни минус 1 (т.е. 31696) по модулю 31697. Это доказывает, что 31697 на самом деле составной. По модулю простого числа остаток 1 не может иметь других квадратных корней, кроме 1 и минус 1. Это показывает, что 31697 не является сильным псевдопростом по основанию 3.

В другом примере выберите n = 47197 и рассчитайте таким же образом:

${\displaystyle 3^{47196}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{23598}\equiv 1{\pmod {47197}}}$

${\displaystyle 3^{11799}\equiv 1{\pmod {47197}}}$

В этом случае результат будет оставаться равным 1 (mod 47197), пока мы не достигнем нечетной экспоненты. В этой ситуации мы говорим, что 47197 - сильное вероятное простое число с основанием 3. Поскольку оказывается, что этот PRP на самом деле составной (можно увидеть, выбрав другие основания, кроме 3), мы имеем, что 47197 - сильное псевдопростое число с основанием 3. .

Наконец, рассмотрим n = 74593, где мы получим:

${\displaystyle 3^{74592}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{37296}\equiv 1{\pmod {74593}}}$

${\displaystyle 3^{18648}\equiv 74592{\pmod {74593}}}$

Здесь мы достигаем минус 1 по модулю 74593, ситуация, которая вполне возможна с простым числом. Когда это происходит, мы останавливаем вычисление (хотя показатель еще не является нечетным) и говорим, что 74593 - сильное вероятное простое число (и, как оказалось, сильное псевдопростое число) с основанием 3.

Формальное определение [ править ]

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

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

или же

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}\quad {\mbox{ for some }}0\leq r<s.}$

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

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

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

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

Сильное псевдопростое число к базовой а всегда является псевдопростое число Эйлера-Якоби , А. Н. Эйлера псевдопростое число ^[2] и псевдопростое число Ферма к этой базе, но не все псевдопростое число Эйлера и Ферма являются сильными псевдопростое число. Числа Кармайкла могут быть сильными псевдопростыми числами для некоторых оснований - например, 561 - сильное псевдопростое число для оснований 50, - но не для всех оснований.

Составное число n является сильным псевдопростом не более чем для четверти всех оснований, меньших n ; ^{[3] [4]} таким образом, не существует «сильных чисел Кармайкла», чисел, которые являются сильными псевдопростыми числами для всех оснований. Таким образом, учитывая случайное основание, вероятность того, что число является сильным псевдопростом по отношению к этому основанию, меньше 1/4, что составляет основу широко используемого критерия простоты Миллера – Рабина . Истинная вероятность отказа обычно намного меньше. Пол Эрдос и Карл Померанс показали в 1986 году, что если случайное целое число n проходит тест простоты Миллера – Рабина до случайного основания b, то n почти наверняка является простым числом . ^[5]Например, из первых 25000000000 положительных целых чисел 1 091 987 405 целых чисел являются вероятными простыми числами с основанием 2, но только 21 853 из них являются псевдопростыми числами, и еще меньше из них являются сильными псевдопростыми числами, поскольку последнее является подмножеством первого. ^[6] Однако Арно ^[7] дает 397-значное число Кармайкла, которое является сильным псевдопростым числом, для каждого основания меньше 307. Один из способов уменьшить вероятность того, что такое число будет ошибочно объявлено простым, - это объединить сильное вероятное простое число. тест с вероятным простым критерием Лукаса , как в тесте на простоту Бейли – PSW .

Сильных псевдопреступлений на любую базу бесконечно много. ^[2]

Примеры [ править ]

Первыми сильными псевдопростыми числами по основанию 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 см. OEIS :  A020230 , а для базы от 6 до 100 см. OEIS : от  A020232 до OEIS :  A020326 . Проверяя вышеуказанные условия на нескольких базах, можно получить несколько более мощные тесты на простоту, чем при использовании только одной базы. Например, есть только 13 чисел меньше 25 · 10 ^9, которые одновременно являются сильными псевдопростыми числами по основанию 2, 3 и 5. Они перечислены в Таблице 7. ^[2] Наименьшее такое число - 25326001. Это означает, что если n меньше 25326001 и n - сильное вероятное простое число с основаниями 2, 3 и 5, то n простое.

Если продолжить, 3825123056546413051 - это наименьшее число, которое является сильным псевдопростом для 9 оснований 2, 3, 5, 7, 11, 13, 17, 19 и 23. ^{[8] [9]} Итак, если n меньше, чем 3825123056546413051 и n - сильное вероятное простое число для этих 9 оснований, тогда n простое.

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

Наименьшее сильное псевдопростое число для базы n [ править ]

Ссылки [ править ]