Квадратичные вычеты и символ Якоби

Bitcoin-адрес из 33 байт содержит сжатую точку эллиптической кривой secp256k1. Один бит - единственный бит - кодирует чётность Y-координаты через символ Лежандра. TLS 1.3 при каждом HTTPS-соединении вычисляет квадратный корень по 256-битному простому через алгоритм Тонелли-Шэнкса. CRYSTALS-Kyber (стандарт NIST post-quantum 2022) использует распределение на $\mathbb{Z}_q$, структуру которого определяют квадратичные вычеты. Квадратичная теория чисел - в каждом браузере, в каждом крипто-кошельке.

• **Bitcoin/Ethereum ECDSA:** сжатый публичный ключ (33 байта vs 65): X-координата + бит чётности Y; восстановление Y = алгоритм Тонелли-Шэнкса за O(log² p)
• **TLS 1.3 ECDH:** при каждом HTTPS-рукопожатии браузер вычисляет sqrt(x³+ax+b) mod p; для secp256k1 быстрый путь: p ≡ 3 (mod 4)
• **Квадратичное решето (QS):** факторизация RSA-129 (1994) и RSA-512 (1999) через поиск x² ≡ y² mod n; символ Якоби определяет factor base
• **CRYSTALS-Kyber (post-quantum):** распределение на Zq, квадратичные вычеты определяют структуру решётки

Предварительные знания

• Теоремы Ферма и Эйлера

Квадратичные вычеты: квадраты в конечном поле

Bitcoin-адрес, начинающийся с `03` или `02`, содержит сжатую точку эллиптической кривой secp256k1. Один бит - единственный бит, который различает эти два префикса - кодирует чётность Y-координаты. Восстановить Y - значит решить уравнение $x^2 \equiv a \pmod{p}$. Вопрос «существует ли такое $x$?» - вопрос о квадратичных вычетах.

**Квадратичный вычет (QR) по модулю $p$:** $a$ - квадратичный вычет mod $p$, если существует $x$: $x^2 \equiv a \pmod{p}$. $a$ - квадратичный невычет (QNR), если такого $x$ нет. **Ключевой факт:** среди $\{1, 2, \ldots, p-1\}$ ровно $\frac{p-1}{2}$ квадратичных вычетов и $\frac{p-1}{2}$ невычетов. **Таблица умножения QR:** - QR $\cdot$ QR = QR - QR $\cdot$ QNR = QNR - QNR $\cdot$ QNR = QR

Ровно половина - это не случайность. Мультипликативная группа $\mathbb{F}_p^*$ циклическая порядка $p-1$. QR - это квадраты в этой группе, то есть образ гомоморфизма $x \mapsto x^2$. Ядро гомоморфизма имеет порядок 2 (элементы $\pm 1$), поэтому образ имеет ровно $\frac{p-1}{2}$ элементов. Симметрия - следствие структуры группы.

Симметрия $x^2 \equiv (p-x)^2 \pmod{p}$ означает, что для проверки QR достаточно перебрать только $x = 1, \ldots, \frac{p-1}{2}$. Каждый из них даёт уникальный квадрат. Поэтому ровно $\frac{p-1}{2}$ различных QR.

Символ Лежандра и критерий Эйлера

TLS 1.3 при каждом HTTPS-соединении выполняет ECDH. Для выработки общего секрета нужно вычислить точку на кривой - а значит, извлечь квадратный корень из трёхчлена $x^3 + ax + b$ по 256-битному простому. Первый шаг - проверить, что корень вообще существует. Это делает символ Лежандра за $O(\log^2 p)$ умножений.

**Символ Лежандра $\left(\frac{a}{p}\right)$:** $$\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{если } p \mid a \\ 1 & \text{если } a \text{ - QR mod } p \\ -1 & \text{если } a \text{ - QNR mod } p \end{cases}$$ **Критерий Эйлера:** $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$ **Свойства:** - Мультипликативность: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right) \cdot \left(\frac{b}{p}\right)$ - $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}$: равен $1$ при $p \equiv 1 \pmod{4}$, равен $-1$ при $p \equiv 3 \pmod{4}$ - $\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}$

secp256k1 (Bitcoin, Ethereum) использует простое $p \equiv 3 \pmod{4}$. Это не случайно: при $p \equiv 3 \pmod{4}$ квадратный корень вычисляется одной формулой $x = a^{(p+1)/4} \bmod p$, без алгоритма Тонелли-Шэнкса. Выбор кривой оптимизирован под производительность.

Закон квадратичной взаимности и символ Якоби

1796 год. Гаусс в 18 лет доказывает теорему, которую позже назовёт «теоремой золотого сечения» - *theorema aureum*. За жизнь он доказал её восемью разными способами. Суть: является ли $p$ квадратом mod $q$ связано с тем, является ли $q$ квадратом mod $p$ - через неожиданно простую формулу.

**Закон квадратичной взаимности (Гаусс, 1796):** Для различных нечётных простых $p, q$: $$\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$$ **Упрощение:** - Если $p \equiv 1 \pmod{4}$ или $q \equiv 1 \pmod{4}$: $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$ - Если $p \equiv q \equiv 3 \pmod{4}$: $\left(\frac{p}{q}\right) = -\left(\frac{q}{p}\right)$ **Символ Якоби $\left(\frac{a}{n}\right)$:** обобщение Лежандра на составной $n = p_1^{e_1} \cdots p_k^{e_k}$: $$\left(\frac{a}{n}\right) = \prod_{i} \left(\frac{a}{p_i}\right)^{e_i}$$ Мультипликативен, но $\left(\frac{a}{n}\right) = 1$ не гарантирует, что $a$ - QR mod $n$.

Алгоритм Якоби - это закон взаимности в процедурной форме. Каждый шаг цикла применяет либо формулу $(2/n)$, либо переворот $(p/q) \leftrightarrow (q/p)$. Работает за $O(\log^2 n)$ без разложения $n$ на множители - именно поэтому используется в тестах простоты Соловэя-Штрассена и Миллера-Рабина.

Алгоритм Тонелли-Шэнкса: квадратный корень mod p

Символ Лежандра отвечает на вопрос «существует ли корень?». Алгоритм Тонелли-Шэнкса его находит. Этот алгоритм работает в OpenSSL, libsecp256k1 (Bitcoin Core), BoringSSL (Chrome/Android). При каждом TLS-рукопожатии браузер выполняет несколько сотен умножений этого алгоритма.

**Алгоритм Тонелли-Шэнкса:** находит $x$: $x^2 \equiv a \pmod{p}$ при $\left(\frac{a}{p}\right) = 1$. **Быстрый случай $p \equiv 3 \pmod{4}$:** $$x = a^{(p+1)/4} \bmod p$$ *Проверка:* $x^2 = a^{(p+1)/2} = a \cdot a^{(p-1)/2} = a \cdot 1 = a$. **Общий случай ($p \equiv 1 \pmod{4}$):** разложить $p-1 = 2^s \cdot q$ (нечётное $q$), найти QNR $z$, итеративно улучшать приближение. Сложность: $O(\log^2 p)$ умножений. **Альтернатива - алгоритм Чиполлы:** работает в расширении $\mathbb{F}_{p^2}$, аналог комплексных чисел. Используется в SageMath.

Квадратичное решето (Quadratic Sieve) - самый быстрый алгоритм факторизации для чисел до ~100 цифр. Именно он использовался для взлома RSA-129 в 1994 году (8 месяцев на 1600 машинах). Его ядро - поиск чисел $x$ таких, что $x^2 \bmod n$ раскладывается только на малые простые из factor base. Символ Якоби $(a/p)$ определяет, какие $a$ вообще могут попасть в factor base.

Ключевые идеи

• **QR:** $a$ - квадратичный вычет mod $p$, если $\exists x: x^2 \equiv a \pmod{p}$; ровно $\frac{p-1}{2}$ вычетов среди $\{1,\ldots,p-1\}$ - следствие структуры $\mathbb{F}_p^*$
• **Символ Лежандра:** $\left(\frac{a}{p}\right) \in \{-1, 0, 1\}$; вычисляется критерием Эйлера $a^{(p-1)/2} \bmod p$ за $O(\log p)$ умножений
• **Взаимность (Гаусс):** $\left(\frac{p}{q}\right) \cdot \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}$ - связывает QR в разных полях без перебора
• **Символ Якоби:** обобщение Лежандра на составной модуль; основа теста Соловэя-Штрассена; $\left(\frac{a}{n}\right) = 1$ не гарантирует QR
• **Тонелли-Шэнкс:** $\sqrt{a} \bmod p$ за $O(\log^2 p)$; при $p \equiv 3 \pmod{4}$ - одна формула $a^{(p+1)/4}$; основа сжатия ECC-точек в Bitcoin/TLS

Связанные темы

Квадратичные вычеты - мост между модулярной арифметикой и криптографией:

• Теоремы Ферма и Эйлера — Критерий Эйлера для QR - прямое применение малой теоремы Ферма
• Тесты простоты — Тест Соловэя-Штрассена использует символ Якоби; Миллер-Рабин - его вероятностное усиление
• Числа в криптографии — ECDSA, Diffie-Hellman, сжатие точек - все используют QR-свойства и алгоритм Тонелли-Шэнкса

Вопросы для размышления

• secp256k1 выбрала p ≡ 3 (mod 4) для ускорения вычисления sqrt. Какой компромисс при выборе другого простого?
• Символ Якоби (a/n) = 1 не означает, что a - QR mod n. Приведите пример с n = 15.
• Квадратичное решето факторизует n через поиск x² ≡ y² mod n. Как закон взаимности ускоряет построение factor base?

Связанные уроки

• nt-04 — Критерий Эйлера - прямое следствие малой теоремы Ферма
• nt-07 — Тест Соловэя-Штрассена строится на символе Якоби
• nt-11 — ECDSA, сжатие точек, Diffie-Hellman - всё использует QR-свойства
• crypto-02-modular-arithmetic