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

Возможная простота является базисом для создания эффективных алгоритмов тестов простоты, которые находят применение в криптографии. Эти алгоритмы обычно являются стохастическими. Идея заключается в том, что пока имеются составные вероятно простые по основанию 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} равно ${\displaystyle ({\tfrac {a}{p}})}$ по основанию p, где ${\displaystyle ({\tfrac {a}{p}})}$ — символ Лежандра. Вероятно простые Эйлера, являющиеся составными, называются псевдопростыми числами Эйлера — Якоби по основанию a.

Этот тест может быть улучшен при использовании факта, что квадратный корень из 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 является также вероятно простым Эйлера по тому же основанию, но не наоборот.

• Псевдопростые Эйлера — Якоби
• Число Кармайкла
• Тест Миллера — Рабина

• The prime glossary — Probable prime
• The PRP Top 10000 (the largest known probable primes)
• Generalized repunit probable primes