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

Содержание

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

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

Скорость

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

Литература

• Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, МЦНМО, 2003
• Трост Э. — Primzahlen / Простые числа — М.: ГИФМЛ, 1959, 135 страниц
• Томас Кормен , Чарльз Лейзерстон , Рональд Ривест , Клиффорд Штайн . Section 31.8: Primality testing // Introduction to Algorithms (рус.) . — Second Edition. — MIT Press; McGraw-Hill, 2001. — С. 889—890. — ISBN 0-262-03293-7 .

Ссылки

• // Berkeley Math Circle 2002—2003
• // Algorithms used in asymmetric cryptosystems.