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

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

Концепція

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

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

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

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

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

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

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