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

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

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

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

• 1 Свойства
• 2 Варианты
  • 2.1 Пример SPRP
• 3 См. также
• 4 Внешние ссылки
• 5 Ссылки

Вероятная простота - основа для эффективных алгоритмов проверки простоты , которые находят применение в криптография. Эти алгоритмы обычно вероятностные i русская природа. Идея состоит в том, что, хотя существуют составные вероятные простые числа, лежащие в основе a для любого фиксированного a, мы можем надеяться, что существует некоторое фиксированное P <1 such that for any given composite n, if we choose a at random, then the probability that n is pseudoprime to base a is at most P. If we repeat this test k times, choosing a new a each time, the probability of n being pseudoprime to all the as tested is hence at most P, and as this decreases exponentially, only moderate k is required to make this probability negligibly small (compared to, for example, the probability of computer hardware error).

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

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

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

Вероятное простое число Эйлера с основанием a - это целое число, которое обозначено простым числом несколько более сильной теоремой о том, что для любого простого числа p a равно $(\; ap)\; \{\backslash \; displaystyle\; (\{\backslash \; tfrac\; \{a\}\; \{p\}\})\}$по модулю p, где $(ap)\; \{\backslash \; displaystyle\; (\{\backslash \; tfrac\; \{a\}\; \{p\}\})\}$- это символ Якоби. Составное вероятное простое число Эйлера называется псевдопростом Эйлера – Якоби для основания a. Наименьшее псевдопростое число Эйлера-Якоби с основанием 2 - 561. Существует 11347 псевдопростых чисел Эйлера-Якоби с основанием 2, которые меньше 25 · 10.

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

$ad\; \equiv \; 1\; (mod\; n),\; \{\backslash \; displaystyle\; a\; ^\; \{d\}\; \backslash \; Equiv\; 1\; \{\backslash \; pmod\; \{n\}\; \},\; \backslash ;\}$

или

$ad\; \cdot \; 2\; r\; \equiv \; -\; 1\; (mod\; n)\; для\; некоторого\; 0\; \le \; r\; \le \; s\; -\; 1.\; \{\backslash \; displaystyle\; a\; ^\; \{d\; \backslash \; cdot\; 2\; ^\; \{r\}\}\; \backslash \; Equiv\; -1\; \{\backslash \; pmod\; \{n\}\}\; \{\backslash \; text\; \{для\; некоторого\}\}\; 0\; \backslash \; leq\; r\; \backslash \; leq\; s-1.\; \backslash ,\}$

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

Наименьшее сильное основание 2 псевдопростых чисел - 2047. Имеется 4842 сильных оснований 2 псевдопростых чисел, которые меньше 25 · 10.

Есть также вероятные простые числа Люка, которые основаны на последовательностях Лукаса. Вероятный простой критерий Лукаса можно использовать отдельно. Тест простоты Бэйли-PSW сочетает в себе тест Лукаса с сильным вероятным тестом простого числа.

Пример SPRP

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

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

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

• Основной глоссарий - Вероятное простое число
• Рейтинг PRP Top 10000 (самые большие известные вероятные простые числа)