Тест Ферма Правити
Багато тестів на простоту засновані на малій теоремі Ферма: якщо просте і не є дільником числа, то
Тестом Ферма на простоту числа за основою називається процедура:
- якщо для підстави і модуля виконується, то може бути простим числом
- якщо, то - однозначно складене.
Тест Міллера Правити
Поліпшення тесту Ферма засноване на твердженні, що для простого, який задовольняє умові
,
слід одне з двох
, .
Будь-яке непарне число можна подати у вигляді
де - непарне. тоді
.
Спочатку обчислюємо і послідовно зводимо в квадрат раз:
.
Для того щоб виконувалася умова
,
необхідним є дотримання одного з 2 умов
.
Якщо одна з умов виконується, то для даного тест повертає "можливо просте"; якщо не виконується, то "однозначно складене".
Імовірнісний тест Міллера - Рабина Правити
Імовірнісний тест Міллера-Рабіна побудований на виборі псевдовипадкових чисел і перевірці тестом Міллера. Якщо для всіх чисел тест пройдено, то називається псевдопростим, і ймовірність того що число не просте, має оцінку
Якщо для якогось числа тест не пройдений, то число складене.