Эйлерова проверка

Эйлерова проверка — это вероятностный тест простоты, основанный на малой теореме Ферма и свойствах символа Лежандра, который позволяет с высокой вероятностью определить, является ли натуральное число составным. В отличие от детерминированных алгоритмов, он не даёт абсолютной гарантии простоты, но обеспечивает вычислительную эффективность и широко применяется в криптографии, теории чисел и алгоритмической комбинаторике.

Определение и математическая основа

Эйлерова проверка базируется на теореме Эйлера, являющейся обобщением малой теоремы Ферма. Для любого целого числа \(a\), взаимно простого с \(n\), выполняется сравнение:

\[ a^{\varphi(n)} \equiv 1 \pmod{n}, \]

где \(\varphi(n)\) — функция Эйлера, равная количеству чисел от 1 до \(n\), взаимно простых с \(n\). Для простого \(n\) функция Эйлера равна \(n-1\), и тогда теорема сводится к малой теореме Ферма:

\[ a^{n-1} \equiv 1 \pmod{n}. \]

Однако эйлерова проверка использует более сильное условие, связанное с символом Лежандра. Для нечётного простого \(p\) и целого \(a\), не кратного \(p\), выполняется:

\[ a^{(p-1)/2} \equiv \left(\frac{a}{p}\right) \pmod{p}, \]

где \(\left(\frac{a}{p}\right)\) — символ Лежандра, равный 1, если \(a\) является квадратичным вычетом по модулю \(p\), и -1, если не является. Если \(n\) — составное, то для некоторых \(a\) это сравнение может нарушаться, что позволяет выявить составную природу числа.

Алгоритм проверки

Эйлерова проверка для заданного нечётного числа \(n > 1\) выполняется следующим образом:

1. Выбирается случайное целое число \(a\) из интервала \(2 \le a \le n-2\).
2. Вычисляется наибольший общий делитель \(\gcd(a, n)\). Если \(\gcd(a, n) \neq 1\), то \(n\) — составное (делится на \(a\)).
3. Вычисляется значение \(x = a^{(n-1)/2} \mod n\).
4. Вычисляется символ Якоби \(\left(\frac{a}{n}\right)\), который для простого \(n\) совпадает с символом Лежандра.
5. Если \(x \not\equiv \left(\frac{a}{n}\right) \pmod{n}\), то \(n\) — составное (свидетель составности).
6. Если \(x \equiv \left(\frac{a}{n}\right) \pmod{n}\), то \(n\) с высокой вероятностью простое (эйлеров псевдопростое по основанию \(a\)).

Для повышения надёжности проверка повторяется с разными основаниями \(a\). Если после \(k\) раундов ни одно основание не дало свидетельства составности, число считается вероятно простым. Вероятность ошибки для одного раунда не превышает 1/2, а для \(k\) раундов — \(1/2^k\).

Свойства и ограничения

Эйлерова проверка является усилением теста Ферма, так как учитывает не только малую теорему Ферма, но и квадратичные вычеты. Однако она не является детерминированной: существуют составные числа, называемые эйлеровыми псевдопростыми, которые проходят проверку для некоторых оснований. Например, число 341 является псевдопростым Ферма по основанию 2, но не проходит эйлерову проверку по тому же основанию, так как \(2^{170} \mod 341 = 1\), а символ Якоби \(\left(\frac{2}{341}\right) = -1\), что даёт расхождение.

Тем не менее, существуют сильные эйлеровы псевдопростые числа, которые проходят проверку для всех оснований, взаимно простых с \(n\). Например, число 561 (число Кармайкла) является эйлеровым псевдопростым по всем основаниям, взаимно простым с ним. Однако такие числа встречаются редко: для чисел до \(10^{12}\) известно лишь несколько десятков сильных эйлеровых псевдопростых.

Сравнение с другими тестами простоты

Эйлерова проверка занимает промежуточное положение между простым тестом Ферма и более сложными вероятностными тестами, такими как тест Миллера — Рабина. Тест Миллера — Рабина является усилением эйлеровой проверки и использует разложение \(n-1\) на степени двойки, что позволяет выявлять большее число составных чисел. Для одного раунда тест Миллера — Рабина имеет вероятность ошибки не более 1/4, что делает его более надёжным при том же количестве итераций.

Сравнительная характеристика:

Применение

Эйлерова проверка используется в задачах, где требуется быстрая проверка простоты с допустимой вероятностью ошибки, но где тест Миллера — Рабина избыточен по сложности. Основные области применения:

• Криптография: генерация больших простых чисел для алгоритмов RSA, Диффи — Хеллмана, Эль-Гамаля. В комбинации с другими тестами (например, тестом Ферма) эйлерова проверка позволяет отсеять большинство составных чисел до применения более точных методов.
• Теория чисел: поиск простых чисел в определённых диапазонах, исследование распределения простых чисел и псевдопростых.
• Алгоритмическая комбинаторика: проверка простоты в задачах, связанных с факторизацией и модульной арифметикой.
• Образовательные цели: изучение вероятностных алгоритмов и теории чисел в университетских курсах.

История

Эйлерова проверка была впервые описана Леонардом Эйлером в XVIII веке в контексте его работ по теории чисел, хотя сам термин «эйлерова проверка» появился значительно позже, в XX веке, с развитием алгоритмической теории чисел. В 1970-х годах, с ростом интереса к криптографии с открытым ключом, вероятностные тесты простоты, включая эйлерову проверку, получили широкое распространение. В 1980 году Майкл Рабин и Гэри Миллер разработали более мощный тест, который стал стандартом де-факто, но эйлерова проверка сохранила своё значение как простой и наглядный пример вероятностного алгоритма.

Интересные факты

• Эйлерова проверка не является самостоятельным тестом для практического использования в криптографии, но часто используется как первый этап в комбинированных алгоритмах, например, в тесте Соловея — Штрассена, который основан на той же идее и имеет аналогичную вероятность ошибки.
• Число 561, являющееся наименьшим числом Кармайкла, одновременно является эйлеровым псевдопростым по всем основаниям, взаимно простым с ним, что демонстрирует ограниченность теста.
• Для чисел до \(10^{10}\) доля эйлеровых псевдопростых среди всех составных чисел составляет менее 0,0001 %, что делает тест практически надёжным для большинства практических задач.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — М.: Вильямс, 2007.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — М.: Вильямс, 2013.
• Молчанов А. В. Теория чисел и криптография. — М.: МЦНМО, 2015.
• Crandall R., Pomerance C. Prime Numbers: A Computational Perspective. — Springer, 2005.