Тест Ферма

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Содержание[править | править код]

Если n — простое число, то оно удовлетворяет сравнению для любого a, которое не делится на n.

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

Скорость[править | править код]

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

Литература[править | править код]

Ссылки[править | править код]