Символ Якоби

k п	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
1	1
3	0	1	−1
5	0	1	−1	−1	1
7	0	1	1	−1	1	−1	−1
9	0	1	1	0	1	1	0	1	1
11	0	1	−1	1	1	1	−1	−1	−1	1	−1
13	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1
15	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1
17	- 0	- 1	1	−1	- 1	−1	−1	−1	1	- 1	−1	−1	−1	1	−1	1	1

Символ Якоби (k/п) для различных k (сверху) и n (слева). Показаны только 0 ≤ k < n , поскольку в соответствии с правилом (2) ниже любое другое k может быть уменьшено по модулю n . Квадратичные вычеты выделены желтым цветом - обратите внимание, что никакая запись с символом Якоби, равным −1, не является квадратичным вычетом, и если k является квадратичным вычетом по модулю взаимно простого n , то (k/п) = 1 , но не все элементы с символом Якоби, равным 1 (см. N = 9 и n = 15 строк), являются квадратичными вычетами. Также обратите внимание, что когда либо n, либо k является квадратом, все значения неотрицательны.

Символ Якоби является обобщением символа Лежандра . Представленный Якоби в 1837 году ^[1], он представляет теоретический интерес для модульной арифметики и других разделов теории чисел , но его основное применение - в вычислительной теории чисел , особенно при проверке простоты и целочисленной факторизации ; они, в свою очередь, важны в криптографии .

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

Для любого целого числа a и любого положительного нечетного целого числа n символ Якоби (а/п) определяется как произведение символов Лежандра, соответствующих простым множителям числа n :

{\ displaystyle \ left ({\ frac {a} {n}} \ right) = \ left ({\ frac {a} {p_ {1}}} \ right) ^ {\ alpha _ {1}} \ left ({\ frac {a} {p_ {2}}} \ right) ^ {\ alpha _ {2}} \ cdots \ left ({\ frac {a} {p_ {k}}} \ right) ^ {\ альфа _ {k}},}

куда

{\ displaystyle n = p_ {1} ^ {\ alpha _ {1}} p_ {2} ^ {\ alpha _ {2}} \ cdots p_ {k} ^ {\ alpha _ {k}}}

- разложение числа n на простые множители .

Символ Лежандра (а/п) определяется для всех целых чисел a и всех нечетных простых чисел p формулой

\left({\frac {a}{p}}\right)=\left\{{\begin{array}{rl}0&{\text{if }}a\equiv 0{\pmod {p}},\\1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and for some integer }}x\colon \;a\equiv x^{2}{\pmod {p}},\\-1&{\text{if }}a\not \equiv 0{\pmod {p}}{\text{ and there is no such }}x.\end{array}}\right.

Следуя обычному соглашению для пустого продукта, (а/1) = 1.

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

Таблица значений [ править ]

Ниже приводится таблица значений символа Якоби (k/п) с n ≤ 59, k ≤ 30, n нечетным.

k п	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21 год	22	23	24	25	26 год	27	28 год	29	30
1	- 1	1	1	- 1	1	1	1	1	- 1	1	1	1	1	1	1	- 1	1	1	1	1	1	1	1	1	- 1	1	1	1	1	1
3	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
5	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0	1	−1	−1	1	0
7	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1	−1	1	−1	−1	0	1	1
9	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0	1	1	0
11	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1	1	−1	0	1	−1	1	1	1	−1	−1	−1
13	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1	−1	−1	−1	−1	1	1	−1	1	0	1	−1	1	1
15	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0	1	1	0	1	0	0	−1	1	0	0	−1	0	−1	−1	0
17	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1	−1	1	1	0	1	1	−1	1	−1	−1	−1	1	1	−1	−1	−1	1
19	1	−1	−1	1	1	1	1	−1	1	−1	1	−1	−1	−1	−1	1	1	−1	0	1	−1	−1	1	1	1	1	−1	1	−1	1
21 год	1	−1	0	1	1	0	0	−1	0	−1	−1	0	−1	0	0	1	1	0	−1	1	0	1	−1	0	1	1	0	0	−1	0
23	1	1	1	1	−1	1	−1	1	1	−1	−1	1	1	−1	−1	1	−1	1	−1	−1	−1	−1	0	1	1	1	1	−1	1	−1
25	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0	1	1	1	1	0
27	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0	1	−1	0
29	1	−1	−1	1	1	1	1	−1	1	−1	−1	−1	1	−1	−1	1	−1	−1	−1	1	−1	1	1	1	1	−1	−1	1	0	1
31 год	1	1	−1	1	1	−1	1	1	1	1	−1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	1	−1	−1	1	−1	−1
33	1	1	0	1	−1	0	−1	1	0	−1	0	0	−1	−1	0	1	1	0	−1	−1	0	0	−1	0	1	−1	0	−1	1	0
35 год	1	−1	1	1	0	−1	0	−1	1	0	1	1	1	0	0	1	1	−1	−1	0	0	−1	−1	−1	0	−1	1	0	1	0
37	1	−1	1	1	−1	−1	1	−1	1	1	1	1	−1	−1	−1	1	−1	−1	−1	−1	1	−1	−1	−1	1	1	1	1	−1	1
39	1	1	0	1	1	0	−1	1	0	1	1	0	0	−1	0	1	−1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0
41 год	1	1	−1	1	1	−1	−1	1	1	1	−1	−1	−1	−1	−1	1	−1	1	−1	1	1	−1	1	−1	1	−1	−1	−1	−1	−1
43 год	1	−1	−1	1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	1	−1	−1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1
45	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0	1	−1	0	1	0	0	−1	−1	0	0	1	0	−1	1	0
47	1	1	1	1	−1	1	1	1	1	−1	−1	1	−1	1	−1	1	1	1	−1	−1	1	−1	−1	1	1	−1	1	1	−1	−1
49	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1	1	1	1	1	0	1	1
51	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	1	0	1	0	0	1	1	0	−1	1	0	1	−1	0	−1	1	0
53	1	−1	−1	1	−1	1	1	−1	1	1	1	−1	1	−1	1	1	1	−1	−1	−1	−1	−1	−1	1	1	−1	−1	1	1	−1
55	1	1	−1	1	0	−1	1	1	1	0	0	−1	1	1	0	1	1	1	−1	0	−1	0	−1	−1	0	1	−1	1	−1	0
57	1	1	0	1	−1	0	1	1	0	−1	−1	0	−1	1	0	1	−1	0	0	−1	0	−1	−1	0	1	−1	0	1	1	0
59	1	−1	1	1	1	−1	1	−1	1	−1	−1	1	−1	−1	1	1	1	−1	1	1	1	1	−1	−1	1	1	1	1	1	−1

Свойства [ править ]

Следующие ниже факты, даже законы взаимности, являются прямым выводом из определения символа Якоби и соответствующих свойств символа Лежандра. ^[2]

Символ Якоби определяется только тогда, когда верхний аргумент («числитель») является целым числом, а нижний аргумент («знаменатель») является положительным нечетным целым числом.

1. Если n - (нечетное) простое число, то символ Якоби (ап) равно (и записывается так же) соответствующему символу Лежандра.

2. Если a ≡ b (mod n ) , то

\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)

3.

\left({\frac {a}{n}}\right)={\begin{cases}0&{\text{if }}\gcd(a,n)\neq 1,\\\pm 1&{\text{if }}\gcd(a,n)=1.\end{cases}}

Если фиксирован верхний или нижний аргумент, символ Якоби является полностью мультипликативной функцией в оставшемся аргументе: ^{[ требуется дальнейшее объяснение ]}

4.

\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right),\quad {\text{so }}\left({\frac {a^{2}}{n}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.

5.

\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right),\quad {\text{so }}\left({\frac {a}{n^{2}}}\right)=\left({\frac {a}{n}}\right)^{2}=1{\text{ or }}0.

Закон квадратичной взаимности : если т и п нечетные положительные взаимно простые числа, то

6.

\left({\frac {m}{n}}\right)\left({\frac {n}{m}}\right)=(-1)^{{\tfrac {m-1}{2}}\cdot {\tfrac {n-1}{2}}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}}{\text{ or }}m\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}

и его добавки

7. ,

\left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}1&{\text{if }}n\equiv 1{\pmod {4}},\\-1&{\text{if }}n\equiv 3{\pmod {4}},\end{cases}}

и $\left({\frac {1}{n}}\right)=\left({\frac {n}{1}}\right)=1$

8.

\left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}1&{\text{if }}n\equiv 1,7{\pmod {8}},\\-1&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}

Объединение свойств 4 и 8 дает:

9.

\left({\frac {2a}{n}}\right)=\left({\frac {2}{n}}\right)\left({\frac {a}{n}}\right)={\begin{cases}\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 1,7{\pmod {8}},\\-\left({\frac {a}{n}}\right)&{\text{if }}n\equiv 3,5{\pmod {8}}.\end{cases}}

Как символ Лежандра:

Если (а/п) = −1, то a - квадратичный невычет по модулю n .

Если a - квадратичный вычет по модулю n и НОД ( a , n ) = 1, то (а/п) = 1.

Но, в отличие от символа Лежандра:

Если (ап) = 1, то a может быть или не быть квадратичным вычетом по модулю n .

Это потому , что для быть квадратичный вычет по модулю п , он должен быть квадратичный вычет по модулю каждый простой множитель из п . Однако символ Якоби равен единице, если, например, a является невычетом по модулю ровно двух простых множителей числа n .

Хотя символ Якоби не может быть интерпретирован единообразно в терминах квадратов и неквадратов, его можно единообразно интерпретировать как знак перестановки по лемме Золотарева .

Символ Якоби (а/п) является характером Дирихле по модулю n .

Вычисление символа Якоби [ править ]

Приведенные выше формулы приводят к эффективному алгоритму O (log a log b ) ^[3] для вычисления символа Якоби, аналогичному алгоритму Евклида для нахождения НОД двух чисел. (Это не должно вызывать удивления в свете правила 2.)

Уменьшите «числитель» по модулю «знаменатель», используя правило 2.
Извлеките любой четный «числитель», используя правило 9.
Если «числитель» равен 1, правила 3 и 4 дают результат 1. Если «числитель» и «знаменатель» не взаимно просты, правило 3 дает результат 0.
В противном случае «числитель» и «знаменатель» теперь являются нечетными положительными взаимно простыми целыми числами, поэтому мы можем перевернуть символ, используя правило 6, а затем вернуться к шагу 1.

Реализация в Lua [ править ]

функция  jacobi ( n ,  k )  assert ( k  >  0  и  k  %  2  ==  1 )  n  =  n  %  k  t  =  1, в  то время как  n  ~ =  0  сделать, в  то время как  n  %  2  ==  0  сделать  n  =  n  /  2  r  =  k  %  8,  если  r  ==  3  или  r  ==  5,  то t  =  - t  end  end  n ,  k  =  k ,  n,  если  n  %  4  ==  3  и  k  %  4  ==  3,  тогда  t  =  - t  end  n  =  n  %  k  end,  если  k  ==  1,  тогда  вернуть  t  иначе  вернуть  0  конец конец

Пример расчетов [ править ]

Символ Лежандра (а/п) определено только для нечетных простых чисел p . Он подчиняется тем же правилам, что и символ Якоби (т.е. взаимность и дополнительные формулы для (−1/п) и (2/п) и мультипликативность «числителя».)

Проблема: учитывая, что 9907 является простым числом, вычислите (105/317) .

Использование символа Лежандра [ править ]

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {7}{9907}}\right)\left({\frac {11}{9907}}\right)\left({\frac {13}{9907}}\right).\\\left({\frac {7}{9907}}\right)&=-\left({\frac {9907}{7}}\right)=-\left({\frac {2}{7}}\right)=-1.\\\left({\frac {11}{9907}}\right)&=-\left({\frac {9907}{11}}\right)=-\left({\frac {7}{11}}\right)=\left({\frac {11}{7}}\right)=\left({\frac {4}{7}}\right)=1.\\\left({\frac {13}{9907}}\right)&=\left({\frac {9907}{13}}\right)=\left({\frac {1}{13}}\right)=1.\\\left({\frac {1001}{9907}}\right)&=-1.\end{aligned}}

Использование символа Якоби [ править ]

{\begin{aligned}\left({\frac {1001}{9907}}\right)&=\left({\frac {9907}{1001}}\right)=\left({\frac {898}{1001}}\right)=\left({\frac {2}{1001}}\right)\left({\frac {449}{1001}}\right)=\left({\frac {449}{1001}}\right)\\&=\left({\frac {1001}{449}}\right)=\left({\frac {103}{449}}\right)=\left({\frac {449}{103}}\right)=\left({\frac {37}{103}}\right)=\left({\frac {103}{37}}\right)\\&=\left({\frac {29}{37}}\right)=\left({\frac {37}{29}}\right)=\left({\frac {8}{29}}\right)=\left({\frac {2}{29}}\right)^{3}=-1.\end{aligned}}

Разница между этими двумя вычислениями заключается в том, что при использовании символа Лежандра «числитель» должен быть разложен на простые степени, прежде чем символ будет перевернут. Это делает вычисления с использованием символа Лежандра значительно медленнее, чем с использованием символа Якоби, поскольку не существует известного алгоритма полиномиального времени для факторизации целых чисел. ^[4] Фактически, именно поэтому Якоби ввел этот символ.

Проверка на первичность [ править ]

Есть еще одна причина различия символов Якоби и Лежандра. Если формула критерия Эйлера используется по модулю составного числа, результатом может быть или не быть значение символа Якоби, а на самом деле может даже не быть -1 или 1. Например,

{\begin{aligned}\left({\frac {19}{45}}\right)&=1&&{\text{ and }}&19^{\frac {45-1}{2}}&\equiv 1{\pmod {45}}.\\\left({\frac {8}{21}}\right)&=-1&&{\text{ but }}&8^{\frac {21-1}{2}}&\equiv 1{\pmod {21}}.\\\left({\frac {5}{21}}\right)&=1&&{\text{ but }}&5^{\frac {21-1}{2}}&\equiv 16{\pmod {21}}.\end{aligned}}

Итак, если неизвестно, является ли число n простым или составным, мы можем выбрать случайное число a , вычислить символ Якоби (а/п) и сравните с формулой Эйлера; если они различаются по модулю n , то n составное; если они имеют одинаковый остаток по модулю n для многих различных значений a , тогда n "вероятно, простое".

Это основа для вероятностного критерия простоты Соловея – Штрассена и таких уточнений, как критерий простоты Бейли-PSW и критерий простоты Миллера – Рабина .

В качестве косвенного использования, можно использовать его в качестве подпрограммы обнаружения ошибок во время выполнения теста на простоту Lucas-Лемер , который, даже на современном компьютерном оборудовании, может занять несколько недель для завершения при обработке чисел Мерсены над (самым большим известным Мерсенна по состоянию на декабрь 2018 г.). В номинальных случаях символ Якоби: ${\begin{aligned}2^{82,589,933}-1\end{aligned}}$

${\begin{aligned}\left({\frac {s_{i}-2}{M_{p}}}\right)&=-1&i\neq 0\end{aligned}}$

Это также относится к окончательному остатку и, следовательно, может использоваться как проверка вероятной достоверности. Однако, если в оборудовании возникает ошибка, существует 50% -ная вероятность того, что вместо этого результат станет 0 или 1 и не изменится с последующими условиями (если только не произойдет другая ошибка и не вернется к -1). ${\begin{aligned}s_{p-2}\end{aligned}}$ ${\begin{aligned}s\end{aligned}}$

См. Также [ править ]

Символ Кронекера , обобщение символа Якоби на все целые числа.
Символ степенного вычета , обобщение символа Якоби на более высокие вычеты.

Заметки [ править ]

^ Якоби, CGJ (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Берлин : 127–136.
^ Ирландия & Rosen стр. 56-57 или Lemmermeyer р. 10
Перейти ↑ Cohen, pp. 29–31
^ Решето числового поля , быстрые известный алгоритм, требует
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
операции к фактору n . См. Cohen, p. 495

Ссылки [ править ]

Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел . Берлин: Springer . ISBN 3-540-55640-0.
Ирландия, Кеннет; Розен, Майкл (1990). Классическое введение в современную теорию чисел (второе издание) . Нью-Йорк: Спрингер . ISBN 0-387-97329-X.
Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна . Берлин: Springer . ISBN 3-540-66957-4.
Шаллит, Джеффри (декабрь 1990). «О худшем случае трех алгоритмов вычисления символа Якоби» . Журнал символических вычислений . 10 (6): 593–61. DOI : 10.1016 / S0747-7171 (08) 80160-5 . Технический отчет по информатике PCS-TR89-140.
Валле, Бриджит ; Леме, Шарли (октябрь 1998 г.). Анализ среднего случая трех алгоритмов вычисления символа Якоби (Технический отчет). CiteSeerX 10.1.1.32.3425 .
Эйкенберри, Шона Мейер; Соренсон, Джонатан П. (октябрь 1998 г.). «Эффективные алгоритмы вычисления символа Якоби» (PDF) . Журнал символических вычислений . 26 (4): 509–523. CiteSeerX 10.1.1.44.2423 . DOI : 10.1006 / jsco.1998.0226 .

Внешние ссылки [ править ]

Символ «Вычислить Якоби» показывает этапы расчета.

[1] Якоби, CGJ (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Берлин : 127–136.

[2] Ирландия & Rosen стр. 56-57 или Lemmermeyer р. 10

[3] Перейти ↑ Cohen, pp. 29–31

[4] Решето числового поля , быстрые известный алгоритм, требует
$O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)$
операции к фактору n . См. Cohen, p. 495

[1],