Вероятное простое число

В теории чисел вероятное простое число ( PRP ) — это целое число , удовлетворяющее определенному условию, которому удовлетворяют все простые числа , но которому не удовлетворяет большинство составных чисел . Различные типы вероятных простых чисел имеют различные определенные условия. Хотя могут быть вероятные простые числа, которые являются составными (называемые псевдопростыми числами ), условие обычно выбирается для того, чтобы сделать такие исключения редкими.

Тест Ферма на составность, основанный на малой теореме Ферма , работает следующим образом: дано целое число n , выбрать некоторое целое число a , которое не кратно n ; (обычно мы выбираем a в диапазоне 1 < a < n − 1 ). Вычислить a ^{n − 1} по модулю n . Если результат не равен 1, то n является составным. Если результат равен 1, то n , скорее всего, будет простым; тогда n называется вероятным простым числом по основанию a . Слабое вероятное простое число по основанию a — это целое число, которое является вероятным простым числом по основанию a , но которое не является сильным вероятным простым числом по основанию a (см. ниже).

Для фиксированного основания a составное число необычно быть вероятным простым числом (то есть псевдопростым числом) по этому основанию. Например, до 25 × 10 ⁹ существует 11 408 012 595 нечетных составных чисел, но только 21 853 псевдопростых числа с основанием 2. ^{[1] : 1005} Количество нечетных простых чисел в том же интервале равно 1 091 987 404.

Характеристики

Вероятная простота является основой для эффективных алгоритмов проверки простоты , которые находят применение в криптографии . Эти алгоритмы обычно являются вероятностными по своей природе. Идея состоит в том, что, хотя существуют составные вероятные простые числа по основанию a для любого фиксированного a , мы можем надеяться, что существует некоторое фиксированное P < 1, такое, что для любого заданного составного n , если мы выберем a случайным образом, то вероятность того, что n является псевдопростым по основанию a, составляет не более P . Если мы повторим этот тест k раз, выбирая каждый раз новое a , вероятность того, что n является псевдопростым по отношению ко всем проверенным a, составляет, следовательно, не более P ^k , и поскольку она уменьшается экспоненциально, требуется только умеренное k, чтобы сделать эту вероятность пренебрежимо малой (по сравнению, например, с вероятностью ошибки компьютерного оборудования).

К сожалению, это неверно для слабых вероятных простых чисел, поскольку существуют числа Кармайкла ; но это верно для более тонких понятий вероятной простоты, таких как сильные вероятные простые числа ( P  = 1/4, алгоритм Миллера–Рабина ) или вероятные простые числа Эйлера ( P  = 1/2, алгоритм Соловея–Штрассена ).

Даже когда требуется детерминированное доказательство простоты, полезным первым шагом будет проверка вероятной простоты. Это может быстро (с уверенностью) исключить большинство составных чисел.

Тест PRP иногда комбинируют с таблицей малых псевдопростых чисел, чтобы быстро установить простоту заданного числа, меньшего некоторого порогового значения.

Вариации

Вероятное простое число Эйлера по основанию a — это целое число, которое определяется как простое с помощью несколько более сильной теоремы, что для любого простого числа p , a ^{( p −1)/2} равно по модулю  p , где — символ Якоби . Вероятное простое число Эйлера, которое является составным, называется псевдопростым числом Эйлера–Якоби по основанию  a . Наименьшее псевдопростое число Эйлера–Якоби по основанию 2 равно 561. ^{[1] : 1004} Существует 11347 псевдопростых чисел Эйлера–Якоби по основанию 2, которые меньше 25·10 ⁹ . ^{[1] : 1005} ${\displaystyle ({\tfrac {a}{p}})}$ ${\displaystyle ({\tfrac {a}{p}})}$

Этот тест можно улучшить, используя тот факт, что единственными квадратными корнями 1 по модулю простого числа являются 1 и −1. Запишите n  =  d  · 2 ^s  + 1, где d нечетно. Число n является сильным вероятным простым числом ( SPRP ) по основанию a , если:

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

или

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

Составное сильное вероятное простое число по основанию a называется сильным псевдопростым числом по основанию a . Каждое сильное вероятное простое число по основанию a также является эйлеровым вероятным простым числом по тому же основанию, но не наоборот.

Наименьшее сильное псевдопростое число с основанием 2 равно 2047. ^{[1] : 1004} Существует 4842 сильных псевдопростых числа с основанием 2, которые меньше 25·10 ⁹ . ^{[1] : 1005}

Существуют также вероятные простые числа Лукаса , которые основаны на последовательностях Лукаса . Тест на вероятные простые числа Лукаса может использоваться отдельно. Тест на простоту Бейли–ПСВ объединяет тест Лукаса с сильным вероятным простым тестом.

Пример проверки на сильное вероятное простое число

Чтобы проверить, является ли число 97 сильным вероятным простым числом по основанию 2:

• Шаг 1: Найти и для которых , где нечетно ${\displaystyle d}$ ${\displaystyle s}$ ${\displaystyle 96=d\cdot 2^{s}}$ ${\displaystyle d}$
  • Начиная с , будет ${\displaystyle s=0}$ ${\displaystyle d}$ ${\displaystyle 96}$
  • Увеличивая , мы видим, что и , поскольку ${\displaystyle s}$ ${\displaystyle d=3}$ ${\displaystyle s=5}$ ${\displaystyle 96=3\cdot 2^{5}}$
• Шаг 2: Выберите , . Мы выберем . ${\displaystyle a}$ ${\displaystyle 1<a<97-1}$ ${\displaystyle a=2}$
• Шаг 3: Вычислить , т.е. . Поскольку это не конгруэнтно , мы продолжаем проверять следующее условие ${\displaystyle a^{d}{\bmod {n}}}$ ${\displaystyle 2^{3}{\bmod {9}}7}$ ${\displaystyle 1}$
• Шаг 4: Вычислите для . Если оно конгруэнтно , то , вероятно, является простым. В противном случае, определенно является составным ${\displaystyle 2^{3\cdot 2^{r}}{\bmod {9}}7}$ ${\displaystyle 0\leq r<s}$ ${\displaystyle 96}$ ${\displaystyle 97}$ ${\displaystyle 97}$
  • ${\displaystyle r=0:2^{3}\equiv 8{\pmod {97}}}$
  • ${\displaystyle r=1:2^{6}\equiv 64{\pmod {97}}}$
  • ${\displaystyle r=2:2^{12}\equiv 22{\pmod {97}}}$
  • ${\displaystyle r=3:2^{24}\equiv 96{\pmod {97}}}$
• Следовательно, является сильным вероятным простым числом с основанием 2 (и, следовательно, является вероятным простым числом с основанием 2). ${\displaystyle 97}$

Смотрите также

• Доказуемое простое число
• Тест простоты Бейли-ПСВ
• Псевдопростое число Эйлера–Якоби
• псевдопростое число Лукаса
• Тест Миллера-Рабина на простоту
• Тест Перрина на простоту
• Число Кармайкла

Внешние ссылки

• Глоссарий основных чисел – Вероятное основное число
• PRP Top 10000 (наибольшие известные вероятные простые числа)

Ссылки

1. Карл Померанс ; Джон Л. Селфридж ; Сэмюэл С. Вагстафф, младший (июль 1980 г.). «Псевдопростые числа до 25·109» (PDF) . Математика вычислений . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 . JSTOR  2006210.