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

Можлива простота є базисом для створення ефективних алгоритмів перевірки простоти, які мають застосування в криптографії. Ці алгоритми зазвичай є стохастичними. Ідея полягає в тому, що поки є складені ймовірно прості за основою 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