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

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

Концепція

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

$a^{p-1}\equiv 1(\mathrm{mod}p).$

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

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

$a^{n-1}\equiv 1(\mathrm{mod}n)$

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

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

$a^{n-1}\equiv ̸1(\mathrm{mod}n)$

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

Приклад

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

$a^{n-1}=38^{220}\equiv 1(\mathrm{mod}221).$

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

$a^{n-1}=26^{220}\equiv 169\equiv ̸1(\mathrm{mod}221).$

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

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

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

Вхід: $n$: значення для тестування на простоту; $k$: параметр, що визначає кількість перевірок
Вихід: складене якщо $n$ є складеним, інакше ймовірно просте
повторити $k$ разів:
   випадково обрати $a$ в діапазоні $[1,n-1]$
   якщо $a^{n-1}\equiv ̸1(\mathrm{mod}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}\equiv ̸1(\mathrm{mod}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},$ що достатньо для практичних цілей.

Примітки

• Шаблон:Cite book