Квадратичный вычет¶

Квадратичный вычет — в теории чисел это целое число \(a\), для которого существует такое целое число \(x\), что \(x^2 \equiv a \pmod{p}\), где \(p\) — модуль, обычно простое число. Если такое \(x\) не существует, то \(a\) называется квадратичным невычетом по модулю \(p\). Понятие квадратичного вычета является фундаментальным в модульной арифметике и находит применение в криптографии, теории кодирования и алгоритмах факторизации.

¶Определение и основные понятия

Пусть \(p\) — нечётное простое число, а \(a\) — целое число, не делящееся на \(p\). Число \(a\) называется квадратичным вычетом по модулю \(p\), если существует такое целое \(x\), что \(x^2 \equiv a \pmod{p}\). В противном случае \(a\) называется квадратичным невычетом по модулю \(p\). Для любого нечётного простого \(p\) ровно половина ненулевых элементов поля \(\mathbb{Z}_p\) являются квадратичными вычетами, а другая половина — невычетами. Число 0 всегда считается квадратичным вычетом, так как \(0^2 \equiv 0 \pmod{p}\).

¶Примеры

По модулю 7 ненулевые квадраты чисел от 1 до 6 дают:

• \(1^2 \equiv 1\)
• \(2^2 \equiv 4\)
• \(3^2 \equiv 2\)
• \(4^2 \equiv 2\)
• \(5^2 \equiv 4\)
• \(6^2 \equiv 1\)

Таким образом, квадратичными вычетами по модулю 7 являются числа 1, 2 и 4; невычетами — 3, 5 и 6.

¶Свойства

¶Мультипликативность

Произведение двух квадратичных вычетов является квадратичным вычетом. Произведение вычета и невычета — невычет. Произведение двух невычетов — вычет. Это свойство следует из того, что множество квадратичных вычетов образует подгруппу индекса 2 в мультипликативной группе \(\mathbb{Z}_p^*\).

¶Символ Лежандра

Для формального описания квадратичных вычетов используется символ Лежандра \(\left(\frac{a}{p}\right)\), который определяется для нечётного простого \(p\) и целого \(a\), не делящегося на \(p\):

\[ \left(\frac{a}{p}\right) = \begin{cases} 1, & \text{если } a \text{ — квадратичный вычет по модулю } p,\\ -1, & \text{если } a \text{ — квадратичный невычет по модулю } p. \end{cases} \]

Для \(a\), кратного \(p\), символ Лежандра полагают равным 0. Символ Лежандра мультипликативен: \(\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \left(\frac{b}{p}\right)\).

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

Критерий Эйлера даёт простой способ проверки, является ли число квадратичным вычетом по модулю нечётного простого \(p\):

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

Если \(a^{\frac{p-1}{2}} \equiv 1 \pmod{p}\), то \(a\) — вычет; если \(a^{\frac{p-1}{2}} \equiv -1 \pmod{p}\), то \(a\) — невычет.

¶Квадратичный закон взаимности

Квадратичный закон взаимности, открытый Гауссом, связывает символы Лежандра для двух различных нечётных простых чисел \(p\) и \(q\):

\[ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}. \]

Этот закон позволяет вычислять символ Лежандра без возведения в степень, что особенно важно для больших чисел.

¶Квадратичные вычеты по составному модулю

Понятие квадратичного вычета можно обобщить на составные модули. Для модуля \(n\), не являющегося простым, число \(a\) называется квадратичным вычетом по модулю \(n\), если существует такое \(x\), что \(x^2 \equiv a \pmod{n}\). Если \(n\) — произведение различных простых чисел, то \(a\) является квадратичным вычетом по модулю \(n\) тогда и только тогда, когда оно является квадратичным вычетом по модулю каждого простого делителя \(n\). Для модулей вида \(2^k\) или \(p^k\) существуют свои критерии.

¶Применение

¶Криптография

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

¶Тестирование простоты

Критерий Эйлера используется в некоторых тестах простоты, например, в тесте Соловея — Штрассена. Этот вероятностный тест проверяет, является ли число \(n\) составным, используя символ Якоби (обобщение символа Лежандра на составные модули). Если для случайного \(a\) выполняется \(\left(\frac{a}{n}\right) \not\equiv a^{\frac{n-1}{2}} \pmod{n}\), то \(n\) — составное.

¶Теория кодирования

В теории кодирования квадратичные вычеты используются при построении квадратично-вычетных кодов — класса циклических кодов с хорошими корректирующими свойствами. Например, код Голея (23,12) основан на квадратичных вычетах по модулю 23.

¶Алгоритмы факторизации

Некоторые алгоритмы факторизации, такие как метод квадратичного решета, используют свойства квадратичных вычетов для нахождения нетривиальных делителей больших чисел.

¶История

Понятие квадратичного вычета восходит к работам Леонарда Эйлера (XVIII век), который сформулировал критерий, носящий его имя. Пьер де Ферма изучал свойства квадратичных вычетов в контексте теории чисел. Карл Фридрих Гаусс в своей книге «Арифметические исследования» (1801) систематизировал теорию квадратичных вычетов и доказал квадратичный закон взаимности, назвав его «золотой теоремой». Впоследствии Адриен-Мари Лежандр ввёл символ, носящий его имя, для удобства записи.

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

• Для простого модуля \(p\) количество квадратичных вычетов равно количеству невычетов и составляет \(\frac{p-1}{2}\).
• Символ Лежандра \(\left(\frac{-1}{p}\right)\) равен 1, если \(p \equiv 1 \pmod{4}\), и -1, если \(p \equiv 3 \pmod{4}\). Это означает, что -1 является квадратичным вычетом по модулю простых чисел, сравнимых с 1 по модулю 4.
• Символ \(\left(\frac{2}{p}\right)\) равен 1, если \(p \equiv \pm 1 \pmod{8}\), и -1, если \(p \equiv \pm 3 \pmod{8}\).
• В криптосистеме Рабина, несмотря на её математическую стойкость, расшифрование неоднозначно: из четырёх возможных квадратных корней нужно выбрать правильный, что требует дополнительной информации (например, избыточности сообщения).

¶Источники

• Виноградов И. М. Основы теории чисел. — М.: Наука, 1965.
• Боревич З. И., Шафаревич И. Р. Теория чисел. — М.: Наука, 1985.
• Коблиц Н. Курс теории чисел и криптографии. — М.: Научное издательство, 2001.
• Гаусс К. Ф. Арифметические исследования (Disquisitiones Arithmeticae). — 1801.