Ймовірно просте число

В теорії чисел, ймовірно простим числом (англ. 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} дорівнює ${\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 [Архівовано 22 квітня 2021 у Wayback Machine.]
• The PRP Top 10000 (the largest known probable primes) [Архівовано 20 серпня 2008 у Wayback Machine.]
• Generalized repunit probable primes [Архівовано 22 жовтня 2021 у Wayback Machine.]