Символ Якобі

Символ Якобі — в теорії чисел узагальнення символу Лежандра для довільних додатних непарних цілих чисел:

якщо розклад $n$ на прості множники має вигляд $p_{1}^{c_{1}}p_{2}^{c_{2}}\cdots p_{k}^{c_{k}}$, то символ Якобі рівний:

$\left({\frac {a}{n}}\right)=\left({\frac {a}{p_{1}}}\right)^{c_{1}}\left({\frac {a}{p_{2}}}\right)^{c_{2}}\cdots \left({\frac {a}{p_{k}}}\right)^{c_{k}}$

де в правій частині є звичайні символи Лежандра.

Якщо $n$ є простим числом то символ Якобі дорівнює символу Лежандра.

Введена в 1837 році Карлом Якобі.

Властивості

Якщо $a=b\mod n$, то $\left({\frac {a}{n}}\right)=\left({\frac {b}{n}}\right)$

$\left({\frac {a}{n}}\right)=0$ тоді і тільки тоді, коли $a$ і $n$ не є взаємно простими

$\left({\frac {ab}{n}}\right)=\left({\frac {a}{n}}\right)\left({\frac {b}{n}}\right)$

$\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$

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

$\left({\frac {-1}{n}}\right)=1$ якщо $n=1\mod 4$

$\left({\frac {-1}{n}}\right)=-1$ якщо $n=3\mod 4$

$\left({\frac {2}{n}}\right)=1$ якщо $n=1\mod 8$ або $n=7\mod 8$

$\left({\frac {2}{n}}\right)=-1$ якщо $n=3\mod 8$ або $n=5\mod 8$

Узагальнений квадратичний закон взаємності:

$\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{\frac {(m-1)(n-1)}{4}}$

Приклад обчислень

$\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 {4}{29}}\right)\left({\frac {2}{29}}\right)=-1.$

Алгоритм

ЯКОБІ(a, n)^:73

Вхід: непарне ціле число $n\geq 3$ і ціле $a,0\leq a<n.$

Вихід: символ Якобі $\left({\frac {a}{n}}\right)$ (відповідно символ Лежандра, якщо $n$ просте).

1. Якщо $a=0,$ тоді повернути(0).
2. Якщо $a=1,$ тоді повернути(1).
3. Записати $a=2^{e}a_{1},$ де $a_{1}$ непарне.
4. Якщо $e$ парне, тоді покласти $s\gets 1.$ Інакше, покласти $s\gets 1$ якщо $n\equiv \pm 1{\pmod {8}}$ або покласти $s\gets -1,$ якщо $n\equiv \pm 3{\pmod {8}}.$
5. Якщо $n\equiv 3{\pmod {4}}$ і $a_{1}\equiv 3{\pmod {4}},$ тоді покласти $s\gets -s.$
6. Покласти $n_{1}\gets n\mod a_{1}.$
7. Якщо $a_{1}=1$ тоді повернути(s); інакше повернути($s\times$ЯКОБІ$(n_{1},a_{1})$).

Література

• Айерлэнд К., Роузен М. Классическое введение в современную теорию чисел. — Москва : Мир, 1987. — 416 с.(рос.)
• Виноградов И. М. Основы теории чисел. — Москва: ГИТТЛ, 1952.
• Богуш В. М., Мухачов В. А. Криптографічні застосування елементарної теорії чисел^{[недоступне посилання з червень 2019]} — К.: ДУІКТ, 2005. — 176 с., ISBN 966-2970-06-1