Символ Якобі

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle =\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)[1]^:73

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

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

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

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