Тест Ферма

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

Содержание

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

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

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
• Трост Простые числа

Для улучшения этой статьи по математике желательно?: Проставив сноски, внести более точные указания на источники. Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.