Символ Якоби: обобщение Лежандра и тест простоты

Символ Якоби - это естественное обобщение символа Лежандра на нечётный составной знаменатель. Карл Густав Якоби ввёл его в 1837 году, и главный смысл расширения чисто алгоритмический: квадратичный закон взаимности и формулы для $-1$ и $2$ переносятся «как есть», поэтому для составного $n$ значение $\left(\dfrac{a}{n}\right)$ удаётся посчитать за $O(\log n)$ шагов без знания факторизации $n$. Цена обобщения - потеря прямой интерпретации: для составного $n$ равенство $\left(\dfrac{a}{n}\right) = +1$ уже не означает, что $a$ - квадрат по модулю $n$. Именно это «расщепление» алгоритма и семантики дало одну из самых ранних схем вероятностного теста простоты - алгоритм Соловея–Штрассена.

Определение через произведение символов Лежандра

Пусть $n > 1$ - нечётное целое с разложением на простые множители $n = p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$, а $a$ - произвольное целое. Символ Якоби определяется как произведение символов Лежандра по простым делителям с учётом кратностей:

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

Каждый множитель в произведении - это уже знакомый символ Лежандра по простому $p_i$, принимающий значения $+1$, $-1$ или $0$. Поэтому весь символ Якоби принимает значения из $\{+1, -1, 0\}$, и $\left(\dfrac{a}{n}\right) = 0$ ровно тогда, когда $\gcd(a, n) > 1$. Дополнительно по соглашению $\left(\dfrac{a}{1}\right) = 1$ для любого $a$ - это удобно для рекурсии.

Если $n = p$ простое, произведение состоит из одного множителя в первой степени, и символ Якоби совпадает с символом Лежандра - никакого расхождения определений нет. Совместимость намеренная: Якоби строится как мультипликативное продолжение Лежандра с одного простого знаменателя на все нечётные составные.

Маленький пример. Возьмём $n = 15 = 3 \cdot 5$. Тогда $\left(\dfrac{2}{15}\right) = \left(\dfrac{2}{3}\right) \cdot \left(\dfrac{2}{5}\right) = (-1) \cdot (-1) = +1$. Несмотря на ответ $+1$, $2$ не является квадратом по модулю $15$: квадраты по $15$ - это $\{0, 1, 4, 6, 9, 10\}$, и двойки в этом списке нет. Этот пример сразу показывает, почему символ Якоби - не «индикатор вычета», а формальная мультипликативная конструкция.

Принципиальный нюанс: $+1$ не гарантирует квадрата

Этот момент - главное отличие от символа Лежандра, и его пропуск регулярно ломает контрольные. Для простого $p$ значение $\left(\dfrac{a}{p}\right) = +1$ ровно эквивалентно тому, что $a$ - квадратичный вычет по модулю $p$. Для составного $n$ такой эквивалентности нет: $a$ - квадрат по модулю $n$ тогда и только тогда, когда $a$ - квадрат по модулю каждого простого делителя $p_i$ (по китайской теореме об остатках), то есть $\left(\dfrac{a}{p_i}\right) = +1$ для всех $i$. Символ Якоби же отслеживает лишь чётность числа невычетов в произведении: «минус на минус даёт плюс», и информация о том, какие именно множители дали $-1$, теряется.

Иными словами, для составного $n$ верны вложения: $a$ квадрат $\Rightarrow \left(\dfrac{a}{n}\right) = +1$, но обратное неверно. Группа квадратичных вычетов по модулю $n = pq$ - это подгруппа индекса $4$ в $(\mathbb{Z}/n\mathbb{Z})^*$, а ядро символа Якоби - подгруппа индекса $2$. В кольце $\mathbb{Z}/15\mathbb{Z}$ есть $4$ ненулевых класса с символом $+1$, но квадратов всего два. Эта «лишняя половина» - невычеты с символом Якоби $+1$ - лежит в основе криптосистемы Голдвассер–Микали и задачи квадратичных вычетов QRP, на трудности различения этих двух подгрупп без знания факторизации $n$.

Мультипликативность по числителю и по знаменателю

Из определения через произведение символов Лежандра наследуется мультипликативность по числителю: $\left(\dfrac{ab}{n}\right) = \left(\dfrac{a}{n}\right) \left(\dfrac{b}{n}\right)$ для любых целых $a, b$. Это - следствие того, что у символа Лежандра мультипликативность уже есть, а произведение мультипликативных функций мультипликативно.

Есть и менее очевидная вторая мультипликативность - по знаменателю: $\left(\dfrac{a}{mn}\right) = \left(\dfrac{a}{m}\right)\left(\dfrac{a}{n}\right)$ для нечётных взаимно простых $m, n$. Она прямо следует из определения через произведение по простым множителям: простые делители $mn$ - объединение простых делителей $m$ и $n$. Эта двусторонняя мультипликативность позволяет «дробить» и числитель, и знаменатель независимо.

Из мультипликативности и периодичности по $a \pmod n$ следует: чтобы посчитать символ Якоби, достаточно уметь обрабатывать случай $a < 0$ через знак, степени двойки в числителе, и собственно сам символ от нечётного числа к нечётному числу.

Обобщённый закон взаимности и дополнения

Главная теорема, оправдывающая всё построение, - обобщённый квадратичный закон взаимности для символа Якоби. Для нечётных взаимно простых $m, n > 0$:

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

По форме - буква в букву как у Лежандра, только теперь оба аргумента могут быть составными. Доказательство сводится к закону взаимности для Лежандра: разложить $m$ и $n$ на простые, расписать произведение пар, сосчитать сумму экспонент. Дополнения работают так же:

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

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

Это и есть инфраструктура для быстрого алгоритма: после редукции $a \bmod n$, вынесения знака и степеней двойки, остаётся пара нечётных чисел, к которой применяется взаимность.

Алгоритм вычисления без факторизации $n$

Решающий для практики момент: алгоритм работает с $n$ как с «чёрным ящиком» - никакого разложения на простые не требуется. Формально структура та же, что и для Лежандра, но шаги выполняются над символом Якоби напрямую:

1. Редукция: $a \gets a \bmod n$. Если $a = 0$ и $n > 1$ - ответ $0$ (т.е. $\gcd(a, n) > 1$).
2. Знак: если $a < 0$, заменить $a \gets -a$ и домножить ответ на $(-1)^{(n-1)/2}$.
3. Двойки: вынести из $a$ все степени двойки $a = 2^k \cdot a'$, домножить ответ на $(-1)^{k(n^2-1)/8}$.
4. Если $a' = 1$ - текущий накопленный знак и есть ответ.
5. Взаимность: поменять местами $a'$ и $n$, домножив на $(-1)^{(a'-1)(n-1)/4}$. Теперь символ выглядит как $\left(\dfrac{n}{a'}\right)$ с $n > a'$.
6. Вернуться к шагу 1.

На каждом цикле либо числитель сокращается по модулю меньшего знаменателя, либо роли меняются местами - поведение точно как у бинарного алгоритма Евклида. Общее число итераций - $O(\log n)$, битовая сложность - $O(\log^2 n)$. Для $1024$-битных $n$, типичных для криптографии, это миллисекунды.

Пример: $\left(\dfrac{30}{77}\right)$, где $77 = 7 \cdot 11$. Выносим двойку: $30 = 2 \cdot 15$, $(2/77) = (-1)^{(77^2-1)/8} = (-1)^{741} = -1$, остаётся $-\left(\dfrac{15}{77}\right)$. По взаимности $(15-1)(77-1)/4 = 14 \cdot 19 = 266$, чётно, знак не меняется: $\left(\dfrac{15}{77}\right) = \left(\dfrac{77}{15}\right) = \left(\dfrac{2}{15}\right) = (-1)^{(225-1)/8} = (-1)^{28} = +1$. Итог: $\left(\dfrac{30}{77}\right) = -1$.

Отличие от символа Лежандра

Подытоживая: алгоритмически символы Лежандра и Якоби считаются одной и той же процедурой (бинарный закон взаимности), и для простого $n$ их значения совпадают. Различие - в семантике результата:

• Лежандр $\left(\dfrac{a}{p}\right)$: точная индикаторная функция квадратичных вычетов по простому модулю. $+1$ означает «есть корень», $-1$ - «нет корня».
• Якоби $\left(\dfrac{a}{n}\right)$: мультипликативный характер группы $(\mathbb{Z}/n\mathbb{Z})^*$ порядка $2$, не различающий квадраты и «двойные невычеты». $+1$ необходимо для квадратичности, но не достаточно; $-1$ всё ещё надёжно означает «не квадрат».

Алгоритмическое сходство - фича, а не баг. Якоби - это инструмент для быстрого вычисления выражений, в которые Лежандр входит как сомножитель, и для криптографических протоколов, где факторизация $n$ скрыта.

Тест простоты Соловея–Штрассена

Самое известное приложение символа Якоби - вероятностный тест простоты Соловея–Штрассена (1977). Идея опирается на критерий Эйлера для символа Лежандра. Если $n$ простое, то для любого $a$, взаимно простого с $n$, выполнено сравнение

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

где справа - символ Лежандра (= символ Якоби, для простого $n$ это одно и то же). Если же $n$ составное, то существует хотя бы один $a$, нарушающий сравнение, и более того - таких «свидетелей составности» не меньше половины из обратимых элементов $(\mathbb{Z}/n\mathbb{Z})^*$.

Алгоритм: выбрать случайный $a \in [2, n-1]$, посчитать левую часть (быстрое возведение в степень за $O(\log^3 n)$) и правую часть (быстрый Якоби за $O(\log^2 n)$), сравнить. Если не равны - $n$ точно составное. Если равны - $n$ «вероятно простое». После $k$ независимых проверок вероятность ошибки (когда составное прошло тест) не превосходит $2^{-k}$: при $k = 50$ это ниже, чем вероятность аппаратного сбоя.

Тест Соловея–Штрассена исторически - один из первых вероятностных алгоритмов в духе Монте-Карло, до него простоту проверяли детерминированными перечислениями, экспоненциальными по длине входа - например, через теорему Вильсона с факториалом по модулю. На практике сегодня его вытеснил тест Миллера–Рабина (тот же принцип, но меньше ложноположительных и более компактная проверка), но идея «свидетеля составности» родилась именно здесь, и символ Якоби был ключевым «бесплатным наблюдаемым», на котором всё построилось.

Приложения в криптографии

Помимо теста простоты, символ Якоби встроен в несколько криптографических конструкций:

• Голдвассер–Микали (1982) - первая семантически безопасная схема шифрования с открытым ключом. Открытый ключ $n = pq$, секретный - $p, q$. Бит $0$ кодируется случайным квадратичным вычетом по модулю $n$, бит $1$ - невычетом с символом Якоби $+1$. Различать эти два множества без знания факторизации - это и есть QRP, гипотетически трудная задача.
• Blum–Blum–Shub - псевдослучайный генератор $x_{i+1} = x_i^2 \bmod n$ для $n = pq$ со специальным выбором простых $p, q \equiv 3 \pmod 4$. Безопасность опирается на ту же QRP.
• Доказательства с нулевым разглашением - символ Якоби - типичный публично проверяемый «протокольный наблюдаемый» в задачах вида «докажи, что знаешь $\sqrt{a} \bmod n$, не раскрывая корня».

Типовые задачи

Контрольные обычно сводятся к трём типам. Первый - посчитать конкретный символ Якоби пошагово, демонстрируя владение алгоритмом. Второй - сравнить два пути вычисления: через факторизацию знаменателя (как произведение символов Лежандра) и через бинарный алгоритм взаимности (без факторизации) - ответы должны совпасть. Третий - построить контрпример к импликации «$\left(\dfrac{a}{n}\right) = +1 \Rightarrow a$ - квадрат» для составного $n$, и обычно это $\left(\dfrac{2}{15}\right) = +1$ или близкие варианты.

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

• Считать $+1$ доказательством квадратичности. Для простого знаменателя - да, для составного - нет. Контрпример $\left(\dfrac{2}{15}\right) = +1$ при отсутствии $x$ с $x^2 \equiv 2 \pmod{15}$ - стандартная ловушка.
• Применять закон взаимности к чётному знаменателю. Символ Якоби определён только для нечётных $n$. Для чётных модулей используют расширения вроде символа Кронекера.
• Забывать, что $\left(\dfrac{a}{n}\right) = 0$ при $\gcd(a, n) > 1$. Если в процессе вычисления $a \bmod n$ обнулилось - это сигнал, что $\gcd > 1$, а не «случайный $0$».
• Считать символ Якоби «через определение» в задаче, где факторизация $n$ неизвестна. Бинарный алгоритм взаимности работает быстрее и не требует разложения; именно для этого Якоби и придуман.
• Путать знак в дополнении для $-1$ или $2$. Формулы $(-1)^{(n-1)/2}$ и $(-1)^{(n^2-1)/8}$ зависят от вычета $n$ по модулю $4$ и $8$ соответственно - лучше держать в голове готовые таблицы.

FAQ

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

Почему символ Якоби можно считать без факторизации $n$? Закон взаимности и дополнения для $-1$ и $2$ зависят только от $n \bmod 4$ и $n \bmod 8$ - а это вычисляется напрямую по $n$, без знания простых множителей. Алгоритм меняет местами числитель и знаменатель, уменьшая их по модулю Евклида, и за $O(\log n)$ шагов сводится к тривиальному случаю $\left(\dfrac{1}{m}\right) = 1$. Факторизация всплыла бы только при определении «через произведение», но в работающем алгоритме она не используется.

Что такое тест Соловея–Штрассена и при чём тут Якоби? Это вероятностный тест простоты, основанный на сравнении $a^{(n-1)/2} \equiv \left(\dfrac{a}{n}\right) \pmod n$, где справа - символ Якоби. Для простого $n$ сравнение выполнено для любого $a$ по критерию Эйлера. Для составного $n$ нарушается минимум для половины $a$, поэтому $k$ случайных проб дают вероятность ошибки $\le 2^{-k}$. Якоби здесь критичен: его быстро считают за $O(\log^2 n)$, не зная разложения $n$ - иначе тест был бы бесполезен.

Коротко

Символ Якоби $\left(\dfrac{a}{n}\right) = \prod_i \left(\dfrac{a}{p_i}\right)^{a_i}$ - мультипликативное расширение символа Лежандра на нечётные составные $n$. Он наследует мультипликативность по числителю и знаменателю, обобщённый закон взаимности и формулы для $-1$ и $2$, но теряет прямую связь с квадратичной вычетностью: $+1$ для составного $n$ не означает «есть корень». Ключевое алгоритмическое свойство - вычисление за $O(\log^2 n)$ без знания факторизации $n$, что лежит в основе теста простоты Соловея–Штрассена и криптосистем Голдвассер–Микали и Blum–Blum–Shub.