Символ Якоби

редактировать

kn	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 / n) для различных k (сверху) и n (слева). Только 0 ≤ k < n are shown, since due to rule (2) below any other k can be reduced modulo n. квадратичные вычеты выделены желтым - обратите внимание, что никакая запись с символом Якоби -1 не является квадратичным вычетом, и если k квадратичный вычет по модулю взаимно простого n, то (k / n) = 1, но не все элементы с символом Якоби, равным 1 (см. N = 9 и n = 15 строк), являются квадратичными вычетами. Также обратите внимание, что когда либо n, либо k является квадратом, все значения неотрицательны.

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

Содержание

1 Определение
2 Таблица значений
3 Свойства
4 Вычисление символа Якоби
- 4.1 Реализация в Lua
5 Пример расчетов
- 5.1 Использование символа Лежандра
- 5.2 Использование символа Якоби
6 Тестирование на простоту
7 См. Также
8 Примечания
9 Ссылки
10 Внешние ссылки

Определение

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

(an) = (ap 1) α 1 (ap 2) α 2 ⋯ (apk) α K, {\ 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 \ 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}},}

где

n = p 1 α 1 p 2 α 2 ⋯ пк α К {\ Displaystyle п = п_ {1} ^ {\ альфа _ {1}} р_ {2} ^ {\ альфа _ {2}} \ cdots р_ {к} ^ {\ альфа _ {к}} }

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

- это факторизация числа n на простые множители.

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

(ap) = {0, если a ≡ 0 (mod p), 1, если a 0 ( mod p) и для некоторого целого x: a ≡ x 2 (mod p), - 1, если a ≢ 0 (mod p) и такого x нет. {\ 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 {и для некоторого целого числа}} x \ двоеточие \; a \ Equiv x ^ {2} { \ pmod {p}}, \\ - 1 {\ text {if}} a \ not \ Equiv 0 {\ pmod {p}} {\ text {и такого нет}} x. \ end {array}} \ right.}

\ 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 {и для некоторого целого числа} x \ двоеточие \; a \ Equiv x ^ 2 \ pmod {p}, \\ -1 \ text {if} a \ not \ Equiv 0 \ pmod {p } \ text {а такого нет} x. \ end {array} \ right.

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

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

Таблица значений

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

kn	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

Свойства

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

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

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

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

(an) = (bn) = (a ± m ⋅ nn) {\ displaystyle \ left ({\ frac {a} {n}} \ right) = \ left ({\ frac {b} {n}} \ right) = \ left ({\ frac {a \ pm m \ cdot n} {n}} \ right)}

{\ displaystyle \ left ({ \ frac {a} {n}} \ right) = \ left ({\ frac {b} {n}} \ right) = \ left ({\ frac {a \ pm m \ cdot n} {n}} \ справа)}

(an) = {0, если gcd (a, n) ≠ 1, ± 1, если gcd (a, n) = 1. {\ displaystyle \ left ({\ frac {a} {n}} \ right) = {\ begin {case} 0 {\ text {if}} \ gcd (a, n) \ neq 1, \\\ pm 1 {\ text {if}} \ gcd (a, n) = 1. \ end {case}}}

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

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

(abn) = (an) (bn), поэтому (a 2 n) = (an) 2 = 1 или 0. {\ 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 {или}} 0.}

{\ 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 {или}} 0.}

(amn) = (am) (an), поэтому (an 2) = (an) 2 = 1 или 0. {\ 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 {или}} 0.}

{\ 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 {или}} 0.}

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

(mn) (nm) = (- 1) m - 1 2 ⋅ n - 1 2 = {1, если n ≡ 1 (mod 4) или m ≡ 1 (mod 4), - 1, если n ≡ m ≡ 3 (модуль 4) {\ 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 {или}} m \ Equiv 1 {\ pmod {4}}, \\ - 1 {\ text {if}} n \ Equiv m \ Equiv 3 {\ pmod {4}} \ end {case}} }

{ \ 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 {или} } m \ Equiv 1 {\ pmod {4}}, \\ - 1 {\ text {if}} n \ Equiv m \ Equ 3 {\ pmod { 4}} \ end {case}}}

и приложения к нему

(- 1 n) = (- 1) n - 1 2 = {1, если n ≡ 1 (mod 4), - 1, если n ≡ 3 (mod 4), {\ 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}}}

{\ displaystyle \ left ({\ frac {-1} {n}} \ right) = (- 1) ^ {\ tfrac {n-1} {2}} = {\ begin {cases} 1 {\ text {if}} n \ Equiv 1 {\ pmod {4}}, \\ - 1 {\ text {if} } п \ эквив 3 {\ pmod {4}}, \ end {case}}}

(2 n) = (- 1) n 2 - 1 8 = {1, если n 1, 7 (mod 8), - 1, если n 3, 5 (mod 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} }}

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

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

(2 a n) = (2 n) (a n) = {(a n), если n ≡ 1, 7 (mod 8), - (a n), если n ≡ 3, 5 (mod 8). {\ 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 \ Equ 1,7 {\ pmod {8}}, \\ - \ left ({\ frac {a} {n}} \ right) {\ text {if}} n \ Equiv 3,5 {\ pmod {8}}. \ end {ases}}}

{\ 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}} п \ эквив 3,5 {\ pmod {8}}. \ end {case}}

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

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

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

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

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

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

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

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

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

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

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

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

функция jacobi (n, k) assert (k>0 и k% 2 == 1) n = n% kt = 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 else return 0 end end

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

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

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

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

(1001 9907) = (7 9907) (11 9907) (13 9907). (7 9907) = - (9907 7) = - (2 7) = - 1. (11 9907) = - (9907 11) = - (7 11) = (11 7) = (4 7) = 1. ( 13 9907) = (9907 13) = (1 13) = 1. (1001 9907) = - 1. {\ displaystyle {\ begin {align} \ 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 {align}}}

{\ displaystyle {\ begin {align} \ left ({\ frac {1001} {9907}} \ right) = \ left ({\ frac {7} {9907}} \ right) \ left ({\ frac {11} {9907}} \ right) \ left ({\ frac {13} {9907}} \ справа). \\\ 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 {align}}}

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

(1001 9907) = (9907 1001) = (898 1001) = (2 1001) (449 1001) = (449 1001) = (1001 449) = (103 449) = (449 103) = (37 103) = (103 37) = (29 37) = (37 29) = (8 29) = (2 29) 3 = - 1. {\ displaystyl e {\ begin {align} \ 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 {align}}}

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

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

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

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

(19 45) = 1 и 19 45 - 1 2 1 (мод 45). (8 21) = - 1 но 8 21 - 1 2 ≡ 1 (мод 21). (5 21) = 1, но 5 21 - 1 2 ≡ 16 (мод 21). {\ displaystyle {\ begin {align} \ 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 {align}}}

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

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

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

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

$(si - 2 M p) = - 1 i ≠ 0 {\ displaystyle {\ begin {align} \ left ({\ frac {s_ {i} -2} {M_ { p}}} \ right) = - 1 i \ neq 0 \ end {align}}}$ ${\ displaystyle {\ begin {align} \ left ({\ frac {s_ {i} -2} {M_ p}}} \ right) = - 1 i \ neq 0 \ end {align}}}$

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

См. Также

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

Примечания

Ссылки

Cohen, Henri (1993). Курс вычислительной алгебраической теории чисел. Берлин: Спрингер. ISBN 3-540-55640-0.
Ирландия, Кеннет; Розен, Майкл (1990). Классическое введение в современную теорию чисел (второе издание). Нью-Йорк: Спрингер. ISBN 0-387-97329-X.
Леммермейер, Франц (2000). Законы взаимности: от Эйлера до Эйзенштейна. Берлин: Спрингер. ISBN 3-540-66957-4.

Внешние ссылки

Символ вычисления Якоби показывает этапы вычисления.