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

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

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

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

Допустим, мы хотим выяснить, является ли 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 (мод 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]

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

Сильное псевдопростое число по основанию 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 в OE ЕСТЬ ).

Первыми по основанию 3 являются

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 7900 3, 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 в «Нерешенных проблемах теории чисел» , 2-е изд. Нью-Йорк: Springer-Verlag, стр. 27–30, 1994.
2. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. дои : 10.1090/S0025-5718-1980-0572872-7 .
3. Луи Монье (1980). «Оценка и сравнение двух эффективных алгоритмов вероятностного тестирования простоты». Теоретическая информатика . 12 : 97–108. дои : 10.1016/0304-3975(80)90007-9 .
4. Рабин , Вероятностный алгоритм проверки простоты. Журнал теории чисел , 12 стр. 128–138, 1980.
5. «Вероятные простые числа: насколько вероятно?» . Проверено 23 октября 2020 г.
6. "Глоссарий простых чисел: вероятное простое число" .
7. Ф. Арно (август 1995 г.). «Построение чисел Кармайкла, которые являются сильными псевдопростыми числами по нескольким основаниям». Журнал символических вычислений . 20 (2): 151–161. дои : 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. "Записи СПРП" . Проверено 3 июня 2015 г.