Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

 В теории чисел, вероятно простым числом (, PRP) называетсяцелое число, которое удовлетворяет некоторым условиям, которымудовлетворяют все простые числа. Различные типы вероятно простых имеютразличные условия. Поскольку вероятно простое может быть составным(такие числа называются псевдопростыми), условие выбирается так, чтобысделать эти исключениями редкими.
 Тест Ферма на простоту, основанный на малой теореме Ферма, работаетследующим образом: для данного n, выберем некоторое a,такое, что a и n взаимно просты и вычислимan - 1 по модулю n. Еслирезультат отличается от 1, то n — составное. Если результатравен 1, n может быть простым, но не обязательно; n в этомслучае называется '''(слабым) вероятно простым по основанию a.

Свойства


 Возможная простота является базисом для создания эффективных алгоритмовтестов простоты, которые находят применение в криптографии. Этиалгоритмы обычно являются стохастическими. Идея заключается в том, чтопока имеются составные вероятно простые по основанию a для любогофиксированного a, мы можем надеяться, что существует некотороеP\textless1, такое, что для любого заданного составногоn, если мы выберем a случайно, вероятность, что nпсевдопросто по основанию a, не меньше P. Если мы повторимэтот тест k раз, выбирая каждый раз новое число a,вероятность того, что n будет псевдопростым для всех проверенныхa будет как минимум Pk. Поскольку этавероятность уменьшается экспоненциально, требуется не очень большоеk, чтобы сделать эту вероятность пренебрежительно малой (посравнению, например, с вероятностью возникновения ошибки в процессоре).
 К сожалению, это неверно для слабых вероятно простых чисел, посколькусуществуют числа Кармайкла, но верно для более строгого отбора вероятнопростых чисел, таких, как сильных вероятно простых чисел (P =1/4, Тест Миллера — Рабина), или Вероятно простых Эйлера (P =1/2, Тест Соловея — Штрассена).
 Даже когда требуется детерминированный алгоритм проверки, полезнымпервым шагом будет тест вероятной простоты. Он может быстро исключитьбольшую часть множителей.
 PRP тест иногда комбинируется с таблицей малых псевдопростых длябыстрого доказательства простоты числа, которое меньше некоторогопорогового значения.

Вариации


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

ad1(modn),


ad2r1(modn) for some 0rs1.
 Составное сильное вероятно простое число по основанию aназывается сильно псевдопростым по основанию a. Каждое сильноевероятно простое число по основанию a является также вероятнопростым Эйлера по тому же основанию, но не наоборот.