Символ Якоби

Для термина «Якоби» см. также другие значения.

Символ Якоби — теоретико-числовая функция двух аргументов, введённая К. Якоби в 1837 году. Является квадратичным характером в кольце вычетов.

Карл Густав Якоб Якоби (1804—1851).

Символ Якоби обобщает символ Лежандра на все нечётные числа, большие единицы. Символ Кронекера — Якоби, в свою очередь, обобщает символ Якоби на все целые числа, но в практических задачах символ Якоби играет гораздо более важную роль, чем символ Кронекера — Якоби.

ОпределениеПравить

Пусть $P$$P$  — нечётное, большее единицы число и $P=p_1{p}_2\dots <!--\; \dots \; -->p_n$$P=p_{1}p_{2}\ldots p_{n}$  — его разложение на простые множители (среди $p_1,\dots <!--\; \dots \; -->,p_n$$p_{1},\;\ldots ,\;p_{n}$  могут быть равные). Тогда для произвольного целого числа $a$$a$  символ Якоби определяется равенством:

$\left(\frac{a}{P}\right)=\left(\frac{a}{p_1}\right)\left(\frac{a}{p_2}\right)\cdots <!--\; \cdots \; -->\left(\frac{a}{p_n}\right),$$\left({\frac {a}{P}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),$ 

где $\left(\frac{a}{p_i}\right)$$\left(\frac{a}{p_i}\right)$  — символы Лежандра.

По определению считаем, что $\left(\frac{a}{1}\right)=1$$\left({\frac {a}{1}}\right)=1$  для всех $a$$a$ .

СвойстваПравить

 

Значения символа Якоби для аргументов от 1 до 100.

• Мультипликативность: $\left(\frac{ab}{P}\right)=\left(\frac{a}{P}\right)\left(\frac{b}{P}\right)$$\left({\frac {ab}{P}}\right)=\left({\frac {a}{P}}\right)\left({\frac {b}{P}}\right)$ .
  • В частности, $\left(\frac{a^{2}b}{P}\right)=\left(\frac{b}{P}\right)$$\left({\frac {a^{2}b}{P}}\right)=\left({\frac {b}{P}}\right)$ .
• Периодичность: если $a\equiv <!--\; \equiv \; -->b(\mathrm{mod}P)$$a\equiv b{\pmod {P}}$ , то $\left(\frac{a}{P}\right)=\left(\frac{b}{P}\right);$$\left({\frac {a}{P}}\right)=\left({\frac {b}{P}}\right);$ 
• $\left(\frac{1}{P}\right)=1;$$\left({\frac {1}{P}}\right)=1;$ 
• $\left(\frac{-<!--\; -\; -->1}{P}\right)=(-<!--\; -\; -->1{)}^{\frac{P-<!--\; -\; -->1}{2}};$$\left({\frac {-1}{P}}\right)=(-1)^{\frac {P-1}{2}};$ 
• $\left(\frac{2}{P}\right)=(-<!--\; -\; -->1{)}^{\frac{P^2-<!--\; -\; -->1}{8}}.$$\left({\frac {2}{P}}\right)=(-1)^{\frac {P^{2}-1}{8}}.$ 
• Если $Q$$Q$  — нечётное натуральное число, взаимно простое с $P$$P$ , то $\left(\frac{Q}{P}\right)\left(\frac{P}{Q}\right)=(-<!--\; -\; -->1{)}^{\frac{P-<!--\; -\; -->1}{2}\cdot <!--\; \cdot \; -->\frac{Q-<!--\; -\; -->1}{2}}$$\left({\frac {Q}{P}}\right)\left({\frac {P}{Q}}\right)=(-1)^{{\frac {P-1}{2}}\cdot {\frac {Q-1}{2}}}$  — аналог квадратичного закона взаимности.
  • В частности, если $P$$P$  и $Q$$Q$  взаимно простые и нечётные, то $\left(\frac{Q}{P}\right)=(-<!--\; -\; -->1{)}^{\frac{P-<!--\; -\; -->1}{2}\cdot <!--\; \cdot \; -->\frac{Q-<!--\; -\; -->1}{2}}\left(\frac{P}{Q}\right)$$\left({\frac {Q}{P}}\right)=(-1)^{{\frac {P-1}{2}}\cdot {\frac {Q-1}{2}}}\left({\frac {P}{Q}}\right)$ .
• Символ Якоби $\left(\frac{a}{P}\right)$$\left({\frac {a}{P}}\right)$  равен знаку перестановки приведённой системы вычетов по модулю $P$$P$ , которая задаётся как умножение элементов этой группы на $a$$a$  (где $a$$a$  обязательно взаимно просто с $P$$P$ ).

Важные замечанияПравить

О вычисленииПравить

Символ Якоби практически никогда не вычисляют по определению. Чаще всего для вычисления используют свойства символа Якоби, главным образом — квадратичный закон взаимности.

Более того, несмотря на то, что символ Якоби является обобщением символа Лежандра и определяется через него, чаще именно символ Лежандра вычисляют с помощью символа Якоби, а не наоборот. См. Пример

О связи с квадратичными сравнениямиПравить

В отличие от символа Лежандра, символ Якоби нельзя напрямую использовать для проверки разрешимости квадратичного сравнения. То есть, если задано сравнение

$x^2\equiv <!--\; \equiv \; -->a\mathrm{mod}n,$$x^{2}\equiv a\mod n,$

((1))

то равенство единице символа Якоби $\left(\frac{a}{n}\right)$$\left({\frac {a}{n}}\right)$  вовсе не означает, что данное сравнение разрешимо. Например, $\left(\frac{2}{15}\right)=(-<!--\; -\; -->1{)}^{28}=1$$\left({\frac {2}{15}}\right)=(-1)^{28}=1$ , но сравнение $x^2\equiv <!--\; \equiv \; -->2\mathrm{mod}15$$x^{2}\equiv 2\mod {15}$  не имеет решений (можно проверить перебором).

Но если $\left(\frac{a}{n}\right)=-<!--\; -\; -->1$$\left({\frac {a}{n}}\right)=-1$ , то сравнение (1) не имеет решений.

Особенность, используемая в тестах простотыПравить

В общем случае неверно, что для символа Якоби выполняется то же условие, что и для символа Лежандра:

$\left(\frac{a}{P}\right)\equiv <!--\; \equiv \; -->a^{\frac{P-<!--\; -\; -->1}{2}}\mathrm{mod}P.$$\left({\frac {a}{P}}\right)\equiv a^{\frac {P-1}{2}}\mod P.$

((2))

Например,

$\left(\frac{7}{15}\right)=\left(\frac{7}{5}\right)\cdot <!--\; \cdot \; -->\left(\frac{7}{3}\right)=\left(\frac{2}{5}\right)\cdot <!--\; \cdot \; -->\left(\frac{1}{3}\right)=(-<!--\; -\; -->1{)}^{\frac{25-<!--\; -\; -->1}{8}}\cdot <!--\; \cdot \; -->1=-<!--\; -\; -->1.$$\left({\frac {7}{15}}\right)=\left({\frac {7}{5}}\right)\cdot \left({\frac {7}{3}}\right)=\left({\frac {2}{5}}\right)\cdot \left({\frac {1}{3}}\right)=(-1)^{\frac {25-1}{8}}\cdot 1=-1.$ 

При этом $7^{\frac{15-<!--\; -\; -->1}{2}}\equiv <!--\; \equiv \; -->7^7\equiv <!--\; \equiv \; -->13\mathrm{mod}15.$$7^{\frac {15-1}{2}}\equiv 7^{7}\equiv 13\mod {15}.$  Числа $a$$a$ , взаимно простые с $P$$P$ , для которых не выполнено условие (2), называются эйлеровыми свидетелями непростоты числа $P$$P$  (поскольку для простого $P$$P$  условие (2) выполнено).

Если $P$$P$  — составное число, то такое число $a$$a$ , для которого условие (2) выполнено, называют лжецом для теста Эйлера.

Доказано, что для любого составного $P$$P$  есть не более $P/2$$P/2$  лжецов, различных по модулю $P$$P$ .

Данное свойство используется в вероятностном тесте Соловея — Штрассена на простоту. В этом алгоритме выбираются случайные числа $a$$a$  и для них проверяется условие (2). Если находится свидетель непростоты, то доказано, что число $P$$P$  — составное. В противном случае говорят, что $P$$P$  — простое с некоторой вероятностью.

Связь с перестановкамиПравить

Пусть $n$$n$  — натуральное число, а $a$$a$  взаимно просто с $n$$n$ . Отображение $m_a:x\to <!--\; \to \; -->ax\mathrm{mod}n$$m_a: x\to ax\mod n$ , действующее на всём $\mathbb{Z}/n\mathbb{Z}$$\mathbb {Z} /n\mathbb {Z}$  определяет перестановку ${\mathrm{\pi <!--\; \pi \; -->}}_a\in <!--\; \in \; -->S_n$$\pi_a\in S_n$ , чётность которой равна символу Якоби:

$\mathrm{\sigma <!--\; \sigma \; -->}({\mathrm{\pi <!--\; \pi \; -->}}_a)=\left(\frac{a}{n}\right)$$\sigma(\pi_a)=\left(\frac{a}{n}\right)$ .

ПрименениеПравить

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

Символ Лежандра, в свою очередь, необходим для проверки разрешимости квадратичного сравнения по модулю простого числа. Но считать его по определению (то есть вычислять $a^{\frac{p-<!--\; -\; -->1}{2}}\mathrm{mod}p$$a^{\frac {p-1}{2}}\mod {p}$ ) — достаточно долгая по времени процедура. С помощью алгоритма быстрого возведения в степень это делается за $O({\log }^3<!--\; \; -->p)$$O(\log ^{3}p)$  битовых операций (если не использовать быстрое умножение и деление). А вычисление символа Якоби требует только $O({\log }^2<!--\; \; -->p)$$O(\log ^{2}p)$  битовых операций.

Символ Якоби используется в некоторых тестах на простоту, например, в (N+1)-методах и, как уже было сказано, в тесте Соловея — Штрассена.

АлгоритмПравить

Основная идеяПравить

Ключевое используемое при вычислении свойство символа Якоби — квадратичный закон взаимности. Благодаря ему алгоритм похож на алгоритм Евклида нахождения наибольшего общего делителя двух чисел, в котором тоже аргументы на каждом шаге меняются местами. Аналогично алгоритму Евклида, при перестановке аргументов больший заменяется на остаток от деления на меньший. Это возможно благодаря периодичности символа Якоби. Однако, поскольку символ Якоби определён только при условии нечётности второго аргумента, то до перестановки выделяется чётная часть первого аргумента.

Формальное описаниеПравить

Входные данные: a — целое число, b — натуральное, нечётное, больше единицы.

Выходные данные: $\left(\frac{a}{b}\right)$$\left(\frac{a}{b}\right)$  — символ Якоби

1 (проверка взаимной простоты). Если НОД (a, b)≠1, выход из алгоритма с ответом 0.

2 (инициализация). r:=1 

3 (переход к положительным числам).
 Если a<0 то
  a:=-a
  Если b mod 4 = 3 то r:=-r
 Конец если

4 (избавление от чётности). t:=0
 Цикл ПОКА a – чётное
  t:=t+1
  a:=a/2
 Конец цикла
 Если t – нечётное, то 
  Если b mod 8 = 3 или 5, то r:=-r.
 Конец если

5 (квадратичный закон взаимности). Если a mod 4 = b mod 4 = 3, то r:=-r.
  c:=a; a:=b mod c; b:=c.

6 (выход из алгоритма?). Если a≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом r.

Комментарии к алгоритмуПравить

В алгоритме везде берётся наименьший положительный вычет (то есть остаток от деления).

На четвёртом шаге используется мультипликативность символа Якоби, а затем вычисляется символ Якоби $\left(\frac{2}{b}\right)=(-<!--\; -\; -->1{)}^{(b^2-<!--\; -\; -->1)/8}$$\left({\frac {2}{b}}\right)=(-1)^{(b^{2}-1)/8}$ . Чтобы избежать лишнего возведения в степень, проверяется только остаток от деления $b$$b$  на 8.

На пятом шаге тоже вместо возведения в степень используется проверка остатков от деления.

Сложность алгоритма равна $O(\log <!--\; \; -->a\cdot <!--\; \cdot \; -->\log <!--\; \; -->b)$$O(\log {a}\cdot \log {b})$  битовых операций.

Пример вычисленияПравить

Вычисление символа Лежандра с помощью символа Якоби:

$\left(\frac{219}{383}\right)=-<!--\; -\; -->\left(\frac{383}{219}\right)=-<!--\; -\; -->\left(\frac{164}{219}\right)=-<!--\; -\; -->\left(\frac{41}{219}\right)=-<!--\; -\; -->\left(\frac{219}{41}\right)=-<!--\; -\; -->\left(\frac{14}{41}\right)=$$\left({\frac {219}{383}}\right)=-\left({\frac {383}{219}}\right)=-\left({\frac {164}{219}}\right)=-\left({\frac {41}{219}}\right)=-\left({\frac {219}{41}}\right)=-\left({\frac {14}{41}}\right)=$ 

$=-<!--\; -\; -->\left(\frac{2}{41}\right)\left(\frac{7}{41}\right)=-<!--\; -\; -->\left(\frac{7}{41}\right)=-<!--\; -\; -->\left(\frac{41}{7}\right)=-<!--\; -\; -->\left(\frac{-<!--\; -\; -->1}{7}\right)=1.$$=-\left({\frac {2}{41}}\right)\left({\frac {7}{41}}\right)=-\left({\frac {7}{41}}\right)=-\left({\frac {41}{7}}\right)=-\left({\frac {-1}{7}}\right)=1.$ 

Список литературыПравить

• Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. — Москва: МЦМНО, 2003. — С. 328. — ISBN 5-94057-103-4..
• Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952. — С. 180. — ISBN 5-93972-252-0.
• Bach E., Shallit J. Algorithmic Number Theory. Vol. I. — Massachusetts: MIT Press, 1996. — ISBN 0-262-02405-5..