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

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

Концепція

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

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

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

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

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

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

Якщо ми обрали ${\displaystyle a}$ таке, що

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

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

Приклад

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

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

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

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

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

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

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

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

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

Вада

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

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

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

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

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

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

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

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

Програма шифрування Pretty Good Privacy (PGP) використовує цей тест у своїх алгоритмах. Шанс утворення числа Кармайкла менш ніж ${\displaystyle 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 .

1. Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)