Тест Ферма

Тест простоты Ферма в теории чисел — это тест простоты натурального числа n, основанный на малой теореме Ферма.

Содержание


 Если n — простое число, то оно удовлетворяет сравнению an11(modn) для любого a, которое не делится на n.
 Выполнение сравнения an11(modn) является необходимым, но не достаточным признаком простоты числа. То есть, если найдётся хотя бы одно a, для которого an11(modn), то число n — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение an11(modn), то число n называют '''псевдопростым по основанию a '''. При проверке числа на простоту тестом Ферма выбирают несколько чисел a. Чем больше количество a, для которых an11(modn), тем больше шансы, что число n простое. Однако существуют составные числа, для которых сравнение an11(modn) выполняется для всех a, взаимно простых с n — это числа Кармайкла. Чисел Кармайкла — бесконечное множество, наименьшее число Кармайкла — 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.

Скорость


 При использовании алгоритмов быстрого возведения в степень по модулю время работы теста Ферма для одного a оценивается как O(log2n × log log n × log log log n), где n - проверяемое число. Обычно проводится несколько проверок с различными a.