Символ Якоби

Символ Якоби — это теоретико-числовая функция, обобщение символа Лежандра на случай нечётного составного модуля. Введён немецким математиком Карлом Густавом Якоби в 1837 году. Символ Якоби используется в теории чисел, криптографии и алгоритмах проверки чисел на простоту, позволяя, в частности, вычислять символ Лежандра без факторизации модуля.

Определение

Пусть \( n \) — нечётное положительное целое число, большее 1, с каноническим разложением на простые множители:

\[ n = p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}, \]

где \( p_i \) — нечётные простые числа, \( e_i \) — натуральные числа. Для целого числа \( a \) символ Якоби \( \left( \frac{a}{n} \right) \) определяется как произведение символов Лежандра по всем простым делителям \( n \):

\[ \left( \frac{a}{n} \right) = \prod_{i=1}^{k} \left( \frac{a}{p_i} \right)^{e_i}, \]

где \( \left( \frac{a}{p_i} \right) \) — символ Лежандра, который равен 0, если \( a \) делится на \( p_i \), и ±1 в противном случае. При \( a = 0 \) или \( \gcd(a, n) \neq 1 \) символ Якоби может быть равен 0, если хотя бы один из множителей равен 0. Если \( n = 1 \), то по определению \( \left( \frac{a}{1} \right) = 1 \) для любого \( a \).

Свойства

Символ Якоби наследует многие свойства символа Лежандра, но с важными отличиями, связанными с тем, что он не является квадратичным символом для составного модуля.

Основные свойства

1. Мультипликативность по числителю:

\[ \left( \frac{ab}{n} \right) = \left( \frac{a}{n} \right) \left( \frac{b}{n} \right) \] для любых целых \( a, b \).

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

\[ \left( \frac{a}{mn} \right) = \left( \frac{a}{m} \right) \left( \frac{a}{n} \right) \] для нечётных взаимно простых \( m, n \).

1. Периодичность:

Если \( a \equiv b \pmod{n} \), то \( \left( \frac{a}{n} \right) = \left( \frac{b}{n} \right) \).

1. Значение при \( a = -1 \):

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

1. Значение при \( a = 2 \):

\[ \left( \frac{2}{n} \right) = (-1)^{\frac{n^2-1}{8}}. \]

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

Для символа Якоби выполняется квадратичный закон взаимности Гаусса в обобщённой форме. Если \( m \) и \( n \) — нечётные взаимно простые положительные числа, то:

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

Это соотношение позволяет эффективно вычислять символ Якоби, сводя его к меньшим модулям, аналогично алгоритму Евклида.

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

Ключевое отличие: если \( n \) — составное число, то равенство \( \left( \frac{a}{n} \right) = 1 \) не означает, что \( a \) является квадратичным вычетом по модулю \( n \). Например, для \( n = 15 \) и \( a = 2 \): \( \left( \frac{2}{15} \right) = \left( \frac{2}{3} \right) \left( \frac{2}{5} \right) = (-1) \cdot (-1) = 1 \), но 2 не является квадратом ни по модулю 3, ни по модулю 5, а значит, и по модулю 15. Если же \( \left( \frac{a}{n} \right) = -1 \), то \( a \) заведомо не является квадратичным вычетом по модулю \( n \).

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

Вычисление символа Якоби \( \left( \frac{a}{n} \right) \) для нечётного \( n > 0 \) и целого \( a \) может быть выполнено рекурсивно с использованием свойств, аналогичных алгоритму Евклида. Основные шаги:

1. Приведение \( a \) по модулю \( n \): заменить \( a \) на \( a \bmod n \).
2. Извлечение степени двойки: если \( a \) чётное, вынести множитель \( 2^k \), используя формулу для \( \left( \frac{2}{n} \right) \).
3. Применение закона взаимности: если \( a \) нечётное и \( a > 1 \), применить закон взаимности, меняя местами \( a \) и \( n \) и учитывая знак.
4. Повторение до тех пор, пока числитель не станет равным 0 или 1.

Этот алгоритм работает за логарифмическое время и не требует факторизации чисел.

Применение

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

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

Теория чисел

В теоретико-числовых исследованиях символ Якоби служит инструментом для изучения квадратичных вычетов и невычетов, а также для построения квадратичных полей и анализа их свойств.

Примеры

Пример 1: Вычислить \( \left( \frac{15}{17} \right) \). Поскольку 17 — простое число, символ Якоби совпадает с символом Лежандра. По закону взаимности: \( \left( \frac{15}{17} \right) = \left( \frac{17}{15} \right) \cdot (-1)^{\frac{15-1}{2} \cdot \frac{17-1}{2}} = \left( \frac{2}{15} \right) \cdot (-1)^{7 \cdot 8} = \left( \frac{2}{15} \right) \). Далее, \( \left( \frac{2}{15} \right) = (-1)^{\frac{15^2-1}{8}} = (-1)^{28} = 1 \). Таким образом, \( \left( \frac{15}{17} \right) = 1 \).

Пример 2: Вычислить \( \left( \frac{7}{15} \right) \). Поскольку 15 = 3·5, имеем \( \left( \frac{7}{15} \right) = \left( \frac{7}{3} \right) \left( \frac{7}{5} \right) \). Символ Лежандра \( \left( \frac{7}{3} \right) = \left( \frac{1}{3} \right) = 1 \), \( \left( \frac{7}{5} \right) = \left( \frac{2}{5} \right) = -1 \). Итого: \( 1 \cdot (-1) = -1 \). Это означает, что 7 не является квадратичным вычетом по модулю 15.

Связь с другими понятиями

Символ Якоби является частным случаем символа Кронекера — Якоби, который обобщается на все целые числа \( n \) (включая чётные и отрицательные). Также существует символ Гильберта, который используется в локальной теории полей классов.

Критика и ограничения

Основное ограничение символа Якоби — невозможность однозначно определить квадратичность по составному модулю. Это делает его менее информативным, чем символ Лежандра, но одновременно и полезным в криптографии, где сложность определения квадратичности является основой безопасности. Кроме того, символ Якоби не является мультипликативным по модулю в том смысле, что его значение не зависит от выбора представления числа \( n \) в виде произведения.

Источники

• К. Айерлэнд, М. Роузен. Классическое введение в современную теорию чисел. — М.: Мир, 1987.
• Г. Дэвенпорт. Высшая арифметика. — М.: Наука, 1965.
• В. В. Прасолов. Многочлены. — М.: МЦНМО, 2001.
• Н. Коблиц. Курс теории чисел и криптографии. — М.: Научное издательство, 2001.