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

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

КонцепціяРедагувати

Мала теорема Ферма стверджує, що якщо   просте число і  , тоді

 

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

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

 

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

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

 

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

ПрикладРедагувати

Припустимо ми хочемо визначити чи є   простим. Випадково оберемо   наприклад   Перевіримо попереднє рівняння:

 

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

 

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

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

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

Вхід:  : значення для тестування на простоту;  : параметр, що визначає кількість перевірок
Вихід: складене якщо   є складеним, інакше ймовірно просте
повторити   разів:
   випадково обрати   в діапазоні  
   якщо  , тоді повернути складене
повернути ймовірно просте

Із використанням швидких алгоритмів для піднесення до степеня за модулем, час виконання становить   де   є числом перевірок, а   — число, яке ми тестуємо на простоту.

ВадаРедагувати

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

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

 

є свідками. Для доведення цього покладемо   свідком, а   брехунами. Тоді

 

і, отже всі   для   є свідками.

Тобто, якщо ми запустили   незалежних перевірок на складеному числі   імовірність, що всі   раз нам трапляться брехуни (тобто, імовірність помилки) становить не більше ніж  

ЗастосуванняРедагувати

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

ПриміткиРедагувати

  • 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. 
  1. Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)