Тест простоти Ферма
Тест простоти Ферма — це імовірнісна перевірка для визначення чи є число ймовірним простим.
Концепція[ред. | ред. код]
Мала теорема Ферма стверджує, що якщо просте число і , тоді
Якщо ми хочемо перевірити на простоту, тоді ми можемо обрати випадкове в інтервалі і подивитись чи виконується рівність. Якщо рівність не зберігається, значить число складене. Якщо рівність виконується для багатьох тоді ми кажемо, що — можливо просте.
Може так статись, що за всіх наших перевірках рівність зберігалась. Будь-яке таке, що
тобто складене, називають брехунами. Якщо перевірка пройдена успішно, називають псевдопростим Ферма по базі .
Якщо ми обрали таке, що
тоді називається свідком складеності .
Приклад[ред. | ред. код]
Припустимо ми хочемо визначити чи є простим. Випадково оберемо наприклад Перевіримо попереднє рівняння:
Або 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.
- ↑ Erdös' upper bound for the number of Carmichael numbers is lower than the prime number function n/log(n)
|