Символ Якобі

Символ Якобі ${\displaystyle \left({\frac {a}{n}}\right)}$ — функція в теорії чисел, що узагальнює символ Лежандра для довільних непарних натуральних чисел ${\displaystyle n}$:

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

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

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

Символ запровадив в 1837 році Карл Якобі.

Властивості

Якщо ${\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})}$).

Див. також

• Характер Діріхле

Примітки

1. Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone (1996). Handbook of Applied Cryptography. CRC Press. с. 73. ISBN 0-8493-8523-7.

Література

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