Символ Якоби - Jacobi symbol

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 (вверху) и п (по левой стороне). Только 0 ≤ k < п показаны, так как по правилу (2) ниже любых других k может быть уменьшен по модулю п. Квадратичные вычеты выделены желтым - обратите внимание, что никакая запись с символом Якоби, равным −1, не является квадратичным вычетом, и если k является квадратичным вычетом по взаимно простому п, тогда (k/п) = 1, но не все записи с символом Якоби 1 (см. п = 9 и п = 15 строки) являются квадратичными вычетами. Также обратите внимание, что когда либо п или же k квадрат, все значения неотрицательны.

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

Определение

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

${\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)^{\alpha _{k}},}$

куда

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

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

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

${\displaystyle \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/п) с п ≤ 59, k ≤ 30, п странный.

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. Если п является (нечетным) простым числом, то символ Якоби (а/п) равно (и записывается так же) соответствующему символу Лежандра.

2. Если а ≡ б (мод п), тогда ${\displaystyle \left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)=\left({\frac {a\pm m\cdot n}{n}}\right)}$

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

8. ${\displaystyle \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. ${\displaystyle \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, тогда а является квадратичным невычетом по модулю п.

• Если а это квадратичный вычет по модулю п и gcd (а,п) = 1, то (а/п) = 1.

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

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

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

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

Символ Якоби (а/п) это Dirichlet персонаж по модулю п.

Вычисление символа Якоби

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

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

Реализация в Lua

функция Якоби(п, k)  утверждать(k > 0 и k % 2 == 1)  п = п % k  т = 1  пока п ~= 0 делать    пока п % 2 == 0 делать      п = п / 2      р = k % 8      если р == 3 или же р == 5 тогда        т = -т      конец    конец    п, k = k, п    если п % 4 == 3 и k % 4 == 3 тогда      т = -т    конец    п = п % k  конец  если k == 1 тогда    возвращаться т  еще    возвращаться 0  конецконец

Пример расчетов

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

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

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

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

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

${\displaystyle {\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. Например,

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

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

Это основа для вероятностного Тест на простоту Соловея – Штрассена и усовершенствования, такие как Тест на простоту Baillie-PSW и Тест на простоту Миллера – Рабина.

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

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

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

Смотрите также

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

Примечания

1. Якоби, К. Дж. Дж. (1837). "Über die Kreisteilung und ihre Anwendung auf die Zahlentheorie". Bericht Ak. Wiss. Берлин: 127–136.
2. Ирландия и Розен стр. 56–57 или Леммермейер стр. 10
3. Коэн, стр. 29–31.
4. В числовое поле сито, самый быстрый из известных алгоритмов, требует

   ${\displaystyle O\left(e^{(\ln N)^{\frac {1}{3}}(\ln \ln N)^{\frac {2}{3}}{\big (}C+o(1){\big )}}\right)}$

   операции по фактору п. См. Cohen, p. 495

Рекомендации

• Коэн, Анри (1993). Курс вычислительной алгебраической теории чисел. Берлин: Springer. ISBN  3-540-55640-0.
• Ирландия, Кеннет; Розен, Майкл (1990). Классическое введение в современную теорию чисел (второе издание). Нью-Йорк: Springer. ISBN  0-387-97329-X.
• Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна. Берлин: Springer. ISBN  3-540-66957-4.
• Шаллит, Джеффри (Декабрь 1990 г.). «О худшем случае трех алгоритмов вычисления символа Якоби». Журнал символических вычислений. 10 (6): 593–61. Дои: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. Дои:10.1006 / jsco.1998.0226.

внешняя ссылка

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