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

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

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

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

Допустим, мы хотим исследовать, является ли 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 на самом деле является составным (оно равно 29×1093). По модулю простого числа остаток 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 · ^2s + 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]

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

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

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

Существует бесконечно много сильных псевдопростых чисел по любому основанию. ^[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 ⁹ , которые являются сильными псевдопростыми числами для оснований 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}}$

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

Ссылки

1. Гай , Псевдопростые числа. Псевдопростые числа Эйлера. Сильные псевдопростые числа. §A12 в Unsolved Problems in Number Theory , 2nd ed. New York: Springer-Verlag, стр. 27-30, 1994.
2. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф-младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
3. Луи Монье (1980). «Оценка и сравнение двух эффективных вероятностных алгоритмов проверки простоты». Теоретическая информатика . 12 : 97–108. doi : 10.1016/0304-3975(80)90007-9 .
4. Рабин , Вероятностный алгоритм проверки простоты. Журнал теории чисел , 12 стр. 128–138, 1980.
5. "Вероятные простые числа: насколько вероятны?" . Получено 23 октября 2020 г. .
6. «Глоссарий основных чисел: вероятные основные числа».
7. Ф. Арно (август 1995 г.). «Построение чисел Кармайкла, являющихся сильными псевдопростыми числами с несколькими основаниями». Журнал символических вычислений . 20 (2): 151–161. doi : 10.1006/jsco.1995.1042 .
8. Чжэньсян Чжан; Мин Тан (2003). «Нахождение сильных псевдопростых чисел с несколькими основаниями. II». Математика вычислений . 72 (244): 2085–2097. doi : 10.1090/S0025-5718-03-01545-X .
9. Цзян, Юпэн; Дэн, Инпу (2012). «Сильные псевдопростые числа по первым 9 простым основаниям». arXiv : 1207.0063v1 [math.NT].
10. "SPRP Records" . Получено 3 июня 2015 г.