Тест Ферма

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

СодержаниеПравить

Если n — простое число, то оно удовлетворяет сравнению $a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$a^{n-1} \equiv 1 \pmod n$  для любого a, которое не делится на n.

Выполнение сравнения $a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$a^{n-1} \equiv 1 \pmod n$  является необходимым, но не достаточным признаком простоты числа. То есть, если найдётся хотя бы одно a, для которого $a^{n-<!--\; -\; -->1}\not\equiv 1(\mathrm{mod}n)$$a^{n-1} \not\equiv 1 \pmod n$ , то число n — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение $a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$a^{n-1} \equiv 1 \pmod n$ , то число n называют псевдопростым по основанию a . При проверке числа на простоту тестом Ферма выбирают несколько чисел a. Чем больше количество a, для которых $a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$a^{n-1} \equiv 1 \pmod n$ , тем больше шансы, что число n простое. Однако существуют составные числа, для которых сравнение $a^{n-<!--\; -\; -->1}\equiv <!--\; \equiv \; -->1(\mathrm{mod}n)$$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.

СсылкиПравить

• Is this number prime? // Berkeley Math Circle 2002—2003
• Fermat’s test // Algorithms used in asymmetric cryptosystems. cryptowiki.net