Тест Ферма

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис

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

Содержание

Если n — простое число, то оно удовлетворяет сравнению [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math] для любого a, которое не делится на n.

Выполнение сравнения [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math] является необходимым, но не достаточным признаком простоты числа. То есть, если найдётся хотя бы одно a, для которого [math]\displaystyle{ a^{n-1} \not\equiv 1 \pmod n }[/math], то число n — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math], то число n называют псевдопростым по основанию a . При проверке числа на простоту тестом Ферма выбирают несколько чисел a. Чем больше количество a, для которых [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math], тем больше шансы, что число n простое. Однако существуют составные числа, для которых сравнение [math]\displaystyle{ a^{n-1} \equiv 1 \pmod n }[/math] выполняется для всех a, взаимно простых с n — это числа Кармайкла. Чисел Кармайкла — бесконечное множество, наименьшее число Кармайкла — 561. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел.

Скорость

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

Литература

Ссылки