Критерий Эйлера

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

Формулировка

Пусть \( p \) — нечётное простое число, а \( a \) — целое число, не делящееся на \( p \). Тогда \( a \) является квадратичным вычетом по модулю \( p \) (то есть существует такое целое \( x \), что \( x^2 \equiv a \pmod{p} \)) тогда и только тогда, когда выполняется сравнение:

\[ a^{(p-1)/2} \equiv 1 \pmod{p}. \]

Если же \( a \) является квадратичным невычетом по модулю \( p \), то:

\[ a^{(p-1)/2} \equiv -1 \pmod{p}. \]

В терминах символа Лежандра критерий Эйлера записывается как:

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

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

Доказательство

Доказательство критерия опирается на малую теорему Ферма, которая утверждает, что для любого \( a \), не кратного \( p \), выполняется \( a^{p-1} \equiv 1 \pmod{p} \). Из этого следует, что \( a^{(p-1)/2} \) является корнем квадратного уравнения \( x^2 \equiv 1 \pmod{p} \), то есть может принимать только значения \( \pm 1 \).

Далее, если \( a \) — квадратичный вычет, то существует \( x \) такое, что \( x^2 \equiv a \pmod{p} \). Тогда:

\[ a^{(p-1)/2} \equiv (x^2)^{(p-1)/2} = x^{p-1} \equiv 1 \pmod{p} \]

по малой теореме Ферма. Если же \( a \) — квадратичный невычет, то можно показать, что \( a^{(p-1)/2} \equiv -1 \pmod{p} \), используя тот факт, что мультипликативная группа поля \( \mathbb{F}_p \) циклическая, и половина её элементов являются квадратами, а половина — нет.

Примеры

Пример 1: Проверка числа 2 по модулю 7

Пусть \( p = 7 \), \( a = 2 \). Вычислим \( 2^{(7-1)/2} = 2^3 = 8 \equiv 1 \pmod{7} \). Следовательно, 2 является квадратичным вычетом по модулю 7. Действительно, \( 3^2 = 9 \equiv 2 \pmod{7} \).

Пример 2: Проверка числа 3 по модулю 7

Для \( a = 3 \) имеем \( 3^3 = 27 \equiv 6 \equiv -1 \pmod{7} \). Значит, 3 — квадратичный невычет по модулю 7. Проверка: квадраты чисел по модулю 7 — это 1, 2, 4, и среди них нет 3.

Пример 3: Проверка числа 5 по модулю 11

\( p = 11 \), \( a = 5 \). \( 5^{(11-1)/2} = 5^5 = 3125 \). Вычислим по модулю 11: \( 5^2 = 25 \equiv 3 \), \( 5^4 \equiv 3^2 = 9 \), \( 5^5 = 5^4 \cdot 5 \equiv 9 \cdot 5 = 45 \equiv 1 \pmod{11} \). Значит, 5 — квадратичный вычет по модулю 11. Действительно, \( 4^2 = 16 \equiv 5 \pmod{11} \).

Свойства и следствия

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

Связь с символом Лежандра

Критерий Эйлера даёт явную формулу для символа Лежандра:

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

где результат интерпретируется как \( 1 \) или \( -1 \) (или \( 0 \) при \( p \mid a \)).

Применение в криптографии

Критерий Эйлера используется в некоторых криптографических протоколах, например, в алгоритме генерации простых чисел или в схемах шифрования, основанных на задаче квадратичного вычета (например, криптосистема Гольдвассер — Микали). В этой криптосистеме открытый ключ включает модуль \( n = pq \), где \( p \) и \( q \) — простые числа, а шифрование основано на том, что определение квадратичного вычета по составному модулю без знания факторизации является вычислительно сложной задачей.

История

Критерий был впервые сформулирован Леонардом Эйлером в 1748 году в его работе «Introductio in analysin infinitorum». Эйлер использовал его для исследования свойств квадратичных вычетов, хотя строгое доказательство в современном виде было дано позднее. Критерий стал важным шагом на пути к формулировке квадратичного закона взаимности, который позже доказал Карл Фридрих Гаусс.

Обобщения

Критерий Эйлера можно обобщить на случай, когда модуль является степенью нечётного простого числа, а также на случай конечных полей. В общем виде для конечного поля \( \mathbb{F}_q \) с \( q = p^n \) элементами элемент \( a \in \mathbb{F}_q^* \) является квадратом тогда и только тогда, когда \( a^{(q-1)/2} = 1 \).

Источники

1. Виноградов И. М. «Основы теории чисел». — М.: Наука, 1972.
2. Айерлэнд К., Роузен М. «Классическое введение в современную теорию чисел». — М.: Мир, 1987.
3. Hardy G. H., Wright E. M. «An Introduction to the Theory of Numbers». — Oxford University Press, 2008.