Символ Лежандра: квадратичные вычеты по простому модулю

Символ Лежандра - это базовый объект элементарной теории чисел, который коротко отвечает на вопрос «является ли число $a$ квадратом по простому модулю $p$». За одной короткой записью $\left(\dfrac{a}{p}\right) \in \{+1, -1, 0\}$ скрывается целая инфраструктура: критерий Эйлера, мультипликативность, квадратичный закон взаимности Гаусса и быстрый алгоритм, который по скорости сопоставим с алгоритмом Евклида. Адриен-Мари Лежандр ввёл этот символ в 1798 году в Essai sur la théorie des nombres, доказательство закона взаимности - целиком заслуга Карла Фридриха Гаусса, который представил восемь разных доказательств в Disquisitiones Arithmeticae (1801).

Определение через квадратичные вычеты

Пусть $p$ - нечётное простое число, $a$ - произвольное целое. Число $a$ называется квадратичным вычетом по модулю $p$, если существует $x$ такое, что $x^2 \equiv a \pmod p$, и квадратичным невычетом в противном случае. Символ Лежандра - это компактная индикаторная функция, которая различает три случая:

$\left(\dfrac{a}{p}\right) = \begin{cases} +1, & \text{если } a \text{ - квадратичный вычет и } p \nmid a, \\ -1, & \text{если } a \text{ - квадратичный невычет}, \\ 0, & \text{если } p \mid a. \end{cases}$

Условие $p \nmid a$ принципиально: ноль формально квадрат ($0 = 0^2$), но его обычно исключают из числа вычетов, чтобы получить мультипликативный гомоморфизм $(\mathbb{Z}/p\mathbb{Z})^* \to \{\pm 1\}$. На ненулевых вычетах символ ведёт себя как характер группы $(\mathbb{Z}/p\mathbb{Z})^*$ порядка два.

В мультипликативной группе $(\mathbb{Z}/p\mathbb{Z})^*$ порядка $p-1$ ровно половина элементов - квадраты, а половина - нет. Это видно из того, что отображение $x \mapsto x^2$ имеет ядро $\{\pm 1\}$, поэтому образ имеет порядок $(p-1)/2$. Значит, квадратичных вычетов ровно $(p-1)/2$ штук, и столько же невычетов - на каждом нечётном простом сумма $\sum_{a=1}^{p-1} \left(\dfrac{a}{p}\right) = 0$.

Маленький пример помогает закрепить определение. Возьмём $p = 7$. Перебираем квадраты ненулевых классов: $1^2 = 1$, $2^2 = 4$, $3^2 = 2$, $4^2 = 2$, $5^2 = 4$, $6^2 = 1$ - все по модулю $7$. Различных квадратов получилось ровно три: $\{1, 2, 4\}$, как и положено по формуле $(p-1)/2 = 3$. Остальные ненулевые классы $\{3, 5, 6\}$ - невычеты. Значит $\left(\dfrac{2}{7}\right) = +1$, $\left(\dfrac{3}{7}\right) = -1$, $\left(\dfrac{0}{7}\right) = 0$. Эта таблица из шести значений - самый прямой способ убедиться, что символ Лежандра вообще существует как объект.

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

Самая прямая формула, переводящая символ Лежандра в арифметику по модулю, - критерий Эйлера:

$a^{(p-1)/2} \equiv \left(\dfrac{a}{p}\right) \pmod p.$

Доказательство держится на малой теореме Ферма: если $p \nmid a$, то $a^{p-1} \equiv 1 \pmod p$, то есть $a^{(p-1)/2}$ - корень уравнения $x^2 - 1 \equiv 0 \pmod p$. У этого уравнения над полем $\mathbb{Z}/p\mathbb{Z}$ ровно два решения, $x \equiv \pm 1$. Поэтому $a^{(p-1)/2}$ принимает только значения $\pm 1$. Если $a = b^2$ - квадрат, то $a^{(p-1)/2} = b^{p-1} \equiv 1 \pmod p$. Среди $(p-1)/2$ квадратов уже все корни уравнения $x^{(p-1)/2} \equiv 1 \pmod p$ исчерпаны (полином степени $(p-1)/2$ имеет ровно столько корней), значит остальные $(p-1)/2$ ненулевых классов дают $-1$ - это и есть невычеты.

Критерий хорош тем, что превращает абстрактный вопрос «есть ли корень?» в задачу быстрого возведения в степень: для $p$ длиной $\ell$ бит вычисление $a^{(p-1)/2} \bmod p$ методом «возведение в квадрат и умножение» занимает $O(\ell^3)$ битовых операций - это полиномиально. Для маленьких $p$ годится и в уме: $\left(\dfrac{2}{7}\right) \equiv 2^3 = 8 \equiv 1 \pmod 7$, значит $2$ - квадрат по модулю $7$ (действительно, $3^2 = 9 \equiv 2$).

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

Прямое следствие критерия Эйлера - символ Лежандра мультипликативен по числителю:

$\left(\dfrac{ab}{p}\right) = \left(\dfrac{a}{p}\right)\left(\dfrac{b}{p}\right).$

Действительно, $(ab)^{(p-1)/2} = a^{(p-1)/2} \cdot b^{(p-1)/2}$, и обе части по модулю $p$ совпадают со значениями символов. Мультипликативность экономит работу: чтобы посчитать $\left(\dfrac{60}{p}\right)$, разложим $60 = 2^2 \cdot 3 \cdot 5$ и получим $\left(\dfrac{60}{p}\right) = \left(\dfrac{2}{p}\right)^2 \cdot \left(\dfrac{3}{p}\right) \cdot \left(\dfrac{5}{p}\right) = \left(\dfrac{3}{p}\right)\left(\dfrac{5}{p}\right)$, поскольку $\left(\dfrac{2}{p}\right)^2 = 1$. То же самое работает для отрицательных $a$: $\left(\dfrac{-a}{p}\right) = \left(\dfrac{-1}{p}\right)\left(\dfrac{a}{p}\right)$.

Из мультипликативности и периодичности по $a$ модуль $p$ ($a \equiv a' \pmod p \Rightarrow \left(\dfrac{a}{p}\right) = \left(\dfrac{a'}{p}\right)$) сразу следует: достаточно уметь считать символ от $-1$, $2$ и нечётных простых $q < p$. Дальше любое $a$ редуцируется по модулю $p$, раскладывается на простые множители и собирается обратно.

Частные значения для -1 и 2

Для $-1$ ответ читается с критерия Эйлера: $\left(\dfrac{-1}{p}\right) = (-1)^{(p-1)/2}$. Это даёт правило:

$\left(\dfrac{-1}{p}\right) = \begin{cases} +1, & p \equiv 1 \pmod 4, \\ -1, & p \equiv 3 \pmod 4. \end{cases}$

Минус единица - квадрат по простому модулю тогда и только тогда, когда $p$ даёт остаток $1$ при делении на $4$. Это утверждение восходит к Ферма и связано с теоремой о представлении простого числа в виде суммы двух квадратов: $p = a^2 + b^2$ возможно для нечётного $p$ ровно тогда, когда $p \equiv 1 \pmod 4$.

Для двойки формула чуть длиннее, доказывается через лемму Гаусса или через сумму Гаусса:

$\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8} = \begin{cases} +1, & p \equiv \pm 1 \pmod 8, \\ -1, & p \equiv \pm 3 \pmod 8. \end{cases}$

Эти две формулы - «дополнения» к основному квадратичному закону взаимности и используются на каждом шаге его применения.

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

Главная теорема, превращающая вычисление символа Лежандра в эффективный алгоритм, - квадратичный закон взаимности (Гаусс, 1796). Для различных нечётных простых $p$ и $q$:

$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right) = (-1)^{\tfrac{p-1}{2} \cdot \tfrac{q-1}{2}}.$

Иначе говоря, $\left(\dfrac{p}{q}\right) = \left(\dfrac{q}{p}\right)$ всегда, кроме случая когда оба простых сравнимы с $3 \pmod 4$ - тогда символы противоположны по знаку. Гаусс называл этот результат «золотой теоремой» (theorema aureum) и за полтора десятилетия дал восемь разных доказательств - через суммы Гаусса, через лемму о подсчёте точек решётки, через теорию циклотомических полиномов. На сегодня известно больше двухсот доказательств, и многие из них работают для разных обобщений (закон взаимности Артина в теории классовых полей - прямой потомок).

Закон взаимности позволяет «поменять числитель и знаменатель местами», после чего числитель обычно становится меньше и можно его редуцировать по новому модулю - задача стремительно сжимается.

Алгоритм вычисления через закон взаимности

Сводя всё вместе, получаем алгоритм, по структуре похожий на алгоритм Евклида:

1. Редуцировать: $a \gets a \bmod p$. Если $a = 0$, ответ $0$.
2. Вынести знак: $\left(\dfrac{a}{p}\right) = \left(\dfrac{-1}{p}\right) \cdot \left(\dfrac{|a|}{p}\right)$ если $a < 0$.
3. Вынести двойки: $a = 2^k \cdot a'$ с нечётным $a'$, тогда $\left(\dfrac{a}{p}\right) = \left(\dfrac{2}{p}\right)^k \cdot \left(\dfrac{a'}{p}\right)$.
4. Если $a' = 1$, ответ $+1$. Иначе $a'$ - нечётное $> 1$, в обозримых задачах оно простое; если нет - разложить и идти по множителям.
5. Применить закон взаимности: $\left(\dfrac{a'}{p}\right) = \pm \left(\dfrac{p}{a'}\right)$, знак считается по чётности $(a'-1)(p-1)/4$.
6. Шаги 1–5 повторяются для меньшего символа.

Пример: $\left(\dfrac{29}{53}\right)$. По взаимности (оба $\equiv 1 \pmod 4$) $\left(\dfrac{29}{53}\right) = \left(\dfrac{53}{29}\right) = \left(\dfrac{24}{29}\right) = \left(\dfrac{2}{29}\right)^3 \left(\dfrac{3}{29}\right) = (-1)^3 \cdot \left(\dfrac{3}{29}\right) = -\left(\dfrac{29}{3}\right) \cdot (-1) = \left(\dfrac{2}{3}\right) = -1$. Получили $-1$, значит $29$ - квадратичный невычет по модулю $53$. Время работы - $O(\ell^2)$ битовых операций для $\ell$-битных чисел, быстрее, чем критерий Эйлера с возведением в степень.

Отличие от символа Якоби

Символ Лежандра определён только для простого знаменателя. Чтобы алгоритм взаимности работал и для составного $n$, его обобщают до символа Якоби $\left(\dfrac{a}{n}\right)$ для нечётных $n > 1$: $n = p_1^{e_1} \cdots p_k^{e_k}$, и по определению

$\left(\dfrac{a}{n}\right) = \prod_{i=1}^k \left(\dfrac{a}{p_i}\right)^{e_i}.$

Внешне символ Якоби ведёт себя так же - мультипликативен, удовлетворяет аналогичному закону взаимности, тем же формулам для $-1$ и $2$. Но, в отличие от символа Лежандра, $\left(\dfrac{a}{n}\right) = +1$ не означает, что $a$ - квадрат по модулю $n$: например, $\left(\dfrac{2}{15}\right) = \left(\dfrac{2}{3}\right) \cdot \left(\dfrac{2}{5}\right) = (-1)(-1) = +1$, но $2$ не является квадратом ни по модулю $15$, ни по модулям $3$ и $5$ по отдельности. Символ Якоби - про чётность числа невычетов в разложении, не про факт квадратичности.

Зато символ Якоби можно считать тем же алгоритмом взаимности, не зная разложения $n$. Это критически важно для криптографии: разложение большого $n$ - трудная задача, а $\left(\dfrac{a}{n}\right)$ вычисляется за $O(\ell^2)$.

Применение в криптографии и тест Соловея-Штрассена

Символы Лежандра и Якоби - основа нескольких криптографических протоколов и тестов простоты. Из практики:

• Тест простоты Соловея-Штрассена (1977): для нечётного $n > 2$ и случайного $a \in [2, n-1]$ проверяется сравнение $a^{(n-1)/2} \equiv \left(\dfrac{a}{n}\right) \pmod n$, где слева - степень, справа - символ Якоби. Если $n$ простое, по критерию Эйлера сравнение верно для всех $a$. Если $n$ составное, по крайней мере половина $a$ нарушает сравнение, поэтому после $k$ независимых проб вероятность ложного «простое» не больше $2^{-k}$. Алгоритм даёт вероятностный тест простоты Монте-Карло, исторически - один из первых.
• Криптосистема Голдвассер–Микали (1982) - первая семантически безопасная схема шифрования: бит $0$ кодируется случайным квадратичным вычетом по модулю $n = pq$, бит $1$ - невычетом с символом Якоби $+1$. Безопасность сводится к гипотезе о трудности задачи квадратичных вычетов (QRP).
• Псевдослучайные генераторы на квадратичных вычетах (Blum–Blum–Shub) - извлекают младший бит $x_{i+1} = x_i^2 \bmod n$, последовательность вычислительно неотличима от случайной при стандартных предположениях о QRP.
• Доказательства с нулевым разглашением - символ Якоби часто служит «бесплатным наблюдаемым», на котором строятся интерактивные протоколы.

Частые ошибки

• Путать с символом Якоби. Если знаменатель составной, $+1$ перестаёт означать «квадрат». Для решения уравнения $x^2 \equiv a \pmod n$ Якоби только необходимый признак, не достаточный.
• Забывать про случай $p \mid a$. Тогда $\left(\dfrac{a}{p}\right) = 0$, а не $\pm 1$. Этот случай обычно отбрасывают на старте, потому что иначе формула $\sum \left(\dfrac{a}{p}\right) = 0$ ломается.
• Применять закон взаимности к $p = 2$. Закон взаимности - про нечётные простые. Двойка обрабатывается отдельной формулой $\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8}$.
• Не вынести знак минус. $\left(\dfrac{-7}{p}\right) \neq \left(\dfrac{7}{p}\right)$ в общем случае. Правильно: $\left(\dfrac{-7}{p}\right) = \left(\dfrac{-1}{p}\right)\left(\dfrac{7}{p}\right)$, и первый множитель зависит от $p \bmod 4$.
• Считать критерий Эйлера в обычной арифметике. $a^{(p-1)/2}$ для больших $p$ - астрономическое число. Нужно возводить в степень по модулю $p$, используя «square-and-multiply» и редукцию на каждом умножении.

FAQ

Чем символ Лежандра отличается от символа Якоби? Лежандр требует простого знаменателя $p$ и тогда $\left(\dfrac{a}{p}\right) = \pm 1, 0$ - точная индикаторная функция квадратичных вычетов. Якоби - мультипликативное расширение на любые нечётные $n$, но равенство $+1$ уже не гарантирует, что $a$ - квадрат по модулю $n$. Алгоритмически их считают одной и той же процедурой (бинарный закон взаимности), но интерпретации разные.

Как быстро считать $\left(\dfrac{a}{p}\right)$ в уме? Свести $a$ к малому представителю $\bmod p$, вынести знак и степени двойки по формулам $\left(\dfrac{-1}{p}\right) = (-1)^{(p-1)/2}$ и $\left(\dfrac{2}{p}\right) = (-1)^{(p^2-1)/8}$, дальше применить закон взаимности. Это аналог алгоритма Евклида: на каждом шаге числа уменьшаются, и общее число шагов - $O(\log p)$. Через критерий Эйлера в уме считать сложнее: $a^{(p-1)/2} \bmod p$ требует длинной цепочки умножений.

Что даёт закон взаимности для алгоритма? Возможность «перевернуть дробь» $\left(\dfrac{p}{q}\right) \leftrightarrow \left(\dfrac{q}{p}\right)$ со знаком, зависящим от $p, q \bmod 4$. После переворота числитель $p$ можно редуцировать по новому модулю $q < p$, и задача сжимается. Без закона взаимности пришлось бы каждый раз поднимать в степень $(p-1)/2$, что медленнее.

Коротко

Символ Лежандра $\left(\dfrac{a}{p}\right)$ - индикатор квадратичного вычета по простому модулю, принимает значения $+1$, $-1$ или $0$. Критерий Эйлера выражает его через степень $a^{(p-1)/2} \bmod p$, мультипликативность по числителю и формулы для $\left(\dfrac{-1}{p}\right)$ и $\left(\dfrac{2}{p}\right)$ позволяют разложить задачу на маленькие куски, а квадратичный закон взаимности Гаусса превращает вычисление в алгоритм типа Евклида за $O(\log p)$ шагов. Обобщение до символа Якоби даёт ту же арифметику без знания разложения модуля и лежит в основе теста простоты Соловея-Штрассена и схемы Голдвассер–Микали.