Символ Якоби

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

Определение


 Пусть P — нечётное, большее единицы число и P=p1p2pn —его разложение на простые множители (среди p1,,pn могутбыть равные). Тогда для произвольного целого числа a символ Якобиопределяется равенством:

(aP)=(ap1)(ap2)(apn),
 где (api) — символы Лежандра.
 По определению считаем, что (a1)=1 для всех a.

Свойства



  • Мультипликативность: (abP)=(aP)(bP).
    • В частности, (a2bP)=(bP).

  • Периодичность: если ab(modP), то (aP)=(bP);
  • (1P)=1;
  • (1P)=(1)P12
  • (2P)=(1)P218.
  • Если Q — нечётное натуральное число, взаимно простое с P, то (QP)(PQ)=(1)P12Q12 — аналог квадратичного закона взаимности.
    • В частности, если P и Q взаимно простые и нечётные, то (QP)=(1)P12Q12(PQ).

  • Символ Якоби (aP) равен знаку перестановки приведённой системы вычетов по модулю P, которая задаётся как умножение элементов этой группы на a (где a обязательно взаимно просто с P).

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


Овычислении


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

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


 В отличие от символа Лежандра, символ Якоби нельзя напрямую использоватьдля проверки разрешимости квадратичного сравнения. То есть, если заданосравнение то равенство единице символа Якоби (an)вовсе не означает, что данное сравнение разрешимо. Например,(215)=(1)28=1, но сравнениеx22mod15 не имеет решений (можно проверить перебором).
 Но если (an)=1, то сравнение (1) не имеетрешений.

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


 В общем случае неверно, что для символа Якоби выполняется то же условие,что и для символа Лежандра: \{mod P.\textbar(2)\}\}Например,

(715)=(75)(73)=(25)(13)=(1)25181=1.
 При этом 715127713mod15. Числа a,взаимно простые с P, для которых не выполнено условие (2), называютсяэйлеровыми свидетелями непростоты числа P (поскольку дляпростого P условие (2) выполнено).
 Если P — составное число, то такое число a, для которого условие(2) выполнено, называют лжецом для теста Эйлера.
 Доказано, что для любого составного P есть не более P/2 лжецов,различных по модулю P.
 Данное свойство используется в вероятностном тесте Соловея — Штрассенана простоту. В этом алгоритме выбираются случайные числа a и для нихпроверяется условие (2). Если находится свидетель непростоты, тодоказано, что число P — составное. В противном случае говорят, чтоP — простое с некоторой вероятностью.

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


 Пусть n - натуральное число, а a взаимно просто с n. Отображениеma:xaxmodn, действующее на всём Z/nZопределяет перестановку πaSn, чётность которой равна символуЯкоби:
σ(πa)=(an).

Применение


 Главным образом, символ Якоби используется для быстрого вычислениясимвола Лежандра.
 Символ Лежандра, в свою очередь, необходим для проверки разрешимостиквадратичного сравнения по модулю простого числа. Но считать его поопределению (то есть вычислять ap12modp) —достаточно долгая по времени процедура. С помощью алгоритма быстроговозведения в степень это делается за O(log3p) битовых операций(если не использовать быстрое умножение и деление). А вычисление символаЯкоби требует только O(log2p) битовых операций.
 Символ Якоби используется в некоторых тестах на простоту, например, в(N+1)-методах и, как уже было сказано, в тесте Соловея — Штрассена.

Алгоритм


Основнаяидея


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

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


Входные данные: a — целое число, b —натуральное, нечётное, больше единицы.
Выходные данные: (ab) — символ Якоби
\texttt1\texttt \texttt(проверка \textttвзаимной\textttпростоты).\texttt Если НОД (\texttta\texttt, \textttb\texttt)≠1, выход из алгоритма с ответом \texttt0\texttt.\\\\\texttt2\texttt \texttt(инициализация).\texttt \textttr\texttt:=1 \\\\\texttt3\texttt \texttt(переход\textttк \textttположительным\textttчислам).\\\texttt \textttЕсли\texttt \texttta\textless0\texttt \textttто\\\texttt  \texttta:=-a\\\texttt  \textttЕсли\texttt \textttb\texttt mod 4 = 3 \textttто\texttt \textttr:=-r\\\texttt \textttКонец\textttесли\\\\\texttt4\texttt \texttt(избавление\textttот\textttчётности).\texttt \textttt\texttt:=0\\\texttt \textttЦикл\texttt ПОКА \texttta\texttt – чётное\\\texttt  \textttt:=t+1\\\texttt  \texttta:=a/2\\\texttt \textttКонец\textttцикла\\\texttt \textttЕсли\texttt \textttt\texttt – нечётное, \textttто\texttt \\\texttt  \textttЕсли\texttt \textttb\texttt mod 8 = 3 или 5, \textttто\texttt \textttr\texttt:=-\textttr\texttt.\\\texttt \textttКонец\textttесли\\\\\texttt5\texttt \texttt(квадратичный\textttзакон\textttвзаимности).\texttt \textttЕсли\texttt \texttta\texttt mod 4 = \textttb\texttt mod 4 = 3, \textttто\texttt \textttr\texttt:=-\textttr\texttt.\\\texttt  c:=a; a:=b mod c; b:=c.\\\\\texttt6\texttt \texttt(выход\textttиз\textttалгоритма?).\texttt Если \texttta\texttt≠0, то идти на шаг 4, иначе выйти из алгоритма с ответом \textttr\texttt.

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


 В алгоритме везде берётся наименьший положительный вычет (то естьостаток от деления).
 На четвёртом шаге используется мультипликативность символа Якоби, азатем вычисляется символ Якоби(2b)=(1)(b21)/8. Чтобы избежать лишнеговозведения в степень, проверяется только остаток от деления b на 8.
 На пятом шаге тоже вместо возведения в степень используется проверкаостатков от деления.
 Сложность алгоритма равна O(logalogb) битовых операций.

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


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

(219383)=(383219)=(164219)=(41219)=(21941)=(1441)=

=(241)(741)=(741)=(417)=(17)=1.

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




 \textbarподзаголовок \textbarзаглавие=Теоретико-числовые алгоритмы вкриптографии \textbarоригинал= \textbarссылка=\textbarавтор=Василенко О.Н. \textbarгод=2003 \textbarместо=Москва \textbarиздательство=МЦМНО \textbarстраницы=328\textbarisbn= 5-94057-103-4 \}\}.


 \textbarзаглавие=Основы теории чисел \textbarссылка=http://www.mccme.ru/free-books/djvu/vinogradov.djvu\textbarавтор= Виноградов И. М. \textbarгод=1952\textbarместо=Москва \textbarиздательство= ГИТТЛ\textbarстраницы=180 \textbarisbn=5-93972-252-0 \}\}


 \textbarподзаголовок \textbarзаглавие= Algorithmic Number Theory.Vol. I \textbarоригинал= \textbarссылка= \textbarавтор=Bach E.,Shallit J. \textbarгод=1996 \textbarместо=Massachusetts\textbarиздательство= MIT Press \textbarстраницы=\textbarisbn=0-262-02405-5 \}\}.
 Категория:Теория чисел