WikiSort.ru - Не сортированное

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

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

Определение

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

${\displaystyle \left({\frac {a}{P}}\right)=\left({\frac {a}{p_{1}}}\right)\left({\frac {a}{p_{2}}}\right)\cdots \left({\frac {a}{p_{n}}}\right),}$

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

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

Свойства

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

Важные замечания

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

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

${\displaystyle x^{2}\equiv a\mod n,}$

((1))

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

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

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

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

${\displaystyle \left({\frac {a}{P}}\right)\equiv a^{\frac {P-1}{2}}\mod P.}$

((2))

Например,

${\displaystyle \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.}$

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

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

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

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

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

Пусть ${\displaystyle n}$ - натуральное число, а ${\displaystyle a}$ взаимно просто с ${\displaystyle n}$ . Отображение ${\displaystyle m_{a}:x\to ax\mod n}$ , действующее на всём ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$ определяет перестановку ${\displaystyle \pi _{a}\in S_{n}}$ , чётность которой равна символу Якоби:

${\displaystyle \sigma (\pi _{a})=\left({\frac {a}{n}}\right)}$ .

Применение

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

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

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

Алгоритм

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.

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

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

${\displaystyle \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)=}$

${\displaystyle =-\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..

В этой статье или разделе имеется список источников или внешних ссылок, но источники отдельных утверждений остаются неясными из-за отсутствия сносок. Утверждения, не подкреплённые источниками, могут быть поставлены под сомнение и удалены. Вы можете улучшить статью, внеся более точные указания на источники.