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

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

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

Свойства

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

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

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

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

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

См. также

Ссылки