Тест Ферма

Тест простоты Ферма в теории чисел — это тест простотынатурального числа 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 logn), где n - проверяемое число. Обычно проводится несколькопроверок с различными a.