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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Концепція

[ред. | ред. код]

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

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

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

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

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

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

Приклад

[ред. | ред. код]

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

Або 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)