Тест простоти Ферма

Тест простоти Ферма — це імовірнісна перевірка для визначення чи є число ймовірним простим.

Концепція

Мала теорема Ферма стверджує, що якщо $p$ просте число і $1\leq a<p$, тоді

$a^{p-1}\equiv 1{\pmod {p}}.$

Якщо ми хочемо перевірити $p$ на простоту, тоді ми можемо обрати випадкове $a$ в інтервалі і подивитись чи виконується рівність. Якщо рівність не зберігається, значить число складене. Якщо рівність виконується для багатьох $a,$ тоді ми кажемо, що $p$ — можливо просте.

Може так статись, що за всіх наших перевірках рівність зберігалась. Будь-яке $a$ таке, що

$a^{n-1}\equiv 1{\pmod {n}}$

тобто $n$ складене, називають брехунами. Якщо перевірка пройдена успішно, $n$ називають псевдопростим Ферма по базі $a$.

Якщо ми обрали $a$ таке, що

$a^{n-1}\not \equiv 1{\pmod {n}}$

тоді $a$ називається свідком складеності $n$.

Приклад

Припустимо ми хочемо визначити чи є $n=221$ простим. Випадково оберемо $1\leq a\leq 221,$ наприклад $a=38.$ Перевіримо попереднє рівняння:

$a^{n-1}=38^{220}\equiv 1{\pmod {221}}.$

Або 221 є простим або 38 є брехун, отже ми беремо інше $a,$ наприклад 26:

$a^{n-1}=26^{220}\equiv 169\not \equiv 1{\pmod {221}}.$

Отже 221 є складеним і 38 дійсно брехун.

Алгоритм і часова складність

Алгоритм можна записати так:

Вхід: $n$: значення для тестування на простоту; $k$: параметр, що визначає кількість перевірок
Вихід: складене якщо $n$ є складеним, інакше ймовірно просте
повторити $k$ разів:
   випадково обрати $a$ в діапазоні $[1,n-1]$
   якщо $a^{n-1}\not \equiv 1{\pmod {n}}$, тоді повернути складене
повернути ймовірно просте

Із використанням швидких алгоритмів для піднесення до степеня за модулем, час виконання становить $O(k\times \log n\times \log \log n\times \log \log \log n),$ де $k$ є числом перевірок, а $n$ — число, яке ми тестуємо на простоту.

Вада

Існує безкінечно багато значень $n$ (відомі як числа Кармайкла) для яких всі значення $a$ для яких $gcd(a,n)=1$ — брехуни. Хоча чисел Кармайкла істотно менше ніж простих,, їх достатньо, щоб часто замість тесту Ферма використовували інші тести простоти такі як тест простоти Міллера-Рабіна та тест простоти Соловея-Штрассена.

Загалом, якщо $n$ не є числом Кармайкла, тоді щонайменше половина всіх

$a\in (\mathbb {Z} /n\mathbb {Z} )^{*}$

є свідками. Для доведення цього покладемо $a$ свідком, а $a_{1},a_{2},\dots ,a_{s}$ брехунами. Тоді

$(a\cdot a_{i})^{n-1}\equiv a^{n-1}\cdot a_{i}^{n-1}\equiv a^{n-1}\not \equiv 1{\pmod {n}}$

і, отже всі $a\times a_{i}$ для $i=1,2,...,s$ є свідками.

Тобто, якщо ми запустили $k$ незалежних перевірок на складеному числі $n,$ імовірність, що всі $k$ раз нам трапляться брехуни (тобто, імовірність помилки) становить не більше ніж $\left({\frac {1}{2}}\right)^{k}.$

Застосування

Програма шифрування Pretty Good Privacy (PGP) використовує цей тест у своїх алгоритмах. Шанс утворення числа Кармайкла менш ніж $1/10^{50},$ що достатньо для практичних цілей.

Примітки

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Section 31.8: Primality testing. Introduction to Algorithms (вид. Second Edition). MIT Press; McGraw-Hill. с. 889–890. ISBN 0-262-03293-7.