Jacobiho symbol

Jacobiho symbol je matematický koncept, zobecnění Legendreova symbolu. Zavedl jej v roce 1837 Carl Jacobi a dnes se řadí do teorie čísel, kde nalézá uplatnění ve výpočtové teorii čísel, zejména v testování prvočíselnosti a rozkládání celých čísel, respektive v jejich aplikacích v kryptografii.

Definice

Nechť je dáno celé číslo a a nějaké liché přirozené číslo n. Pak je Jacobiho symbol definován na základě prvočíselného rozkladu čísla n jako součin:

{\Bigg (}{\frac {a}{n}}{\Bigg )}=\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}},{\mbox{ kde }}n=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\cdots p_{k}^{\alpha _{k}}

Pro n rovno jedné je roven jedné i Jacobiho symbol.

Vlastnosti

Je-li n liché prvočíslo pak se Jacobiho symbol rovná Legendreovu symbolu.
Pokud platí $a\equiv b{\pmod {n}}$ , pak také platí ${\Bigg (}{\frac {a}{n}}{\Bigg )}=\left({\frac {b}{n}}\right)$
Pokud jsou čísla a, n soudělná, je Jacobiho symbol roven 0, jinak nabývá jedné z hodnot +1, −1.
$\left({\frac {ab}{n}}\right)={\Bigg (}{\frac {a}{n}}{\Bigg )}\left({\frac {b}{n}}\right)$ , tedy $\left({\frac {a^{2}}{n}}\right)=1$ (případně $0$ )
$\left({\frac {a}{mn}}\right)=\left({\frac {a}{m}}\right)\left({\frac {a}{n}}\right)$ , tedy $\left({\frac {a}{n^{2}}}\right)=1$ (případně $0$ )
zákon kvadratické reciprocity: Pokud jsou m a n lichá nesoudělná přirozená čísla, pak $\left({\frac {m}{n}}\right)=\left({\frac {n}{m}}\right)(-1)^{{\tfrac {m-1}{2}}{\tfrac {n-1}{2}}}={\begin{cases}\;\;\;\left({\frac {n}{m}}\right)&{\text{pokud }}n\equiv 1{\pmod {4}}{\text{ nebo }}m\equiv 1{\pmod {4}}\\-\left({\frac {n}{m}}\right)&{\text{pokud }}n\equiv m\equiv 3{\pmod {4}}\end{cases}}$
$\left({\frac {-1}{n}}\right)=(-1)^{\tfrac {n-1}{2}}={\begin{cases}\;\;\,1&{\text{pokud }}n\equiv 1{\pmod {4}}\\-1&{\text{pokud }}n\equiv 3{\pmod {4}}\end{cases}}$
$\left({\frac {2}{n}}\right)=(-1)^{\tfrac {n^{2}-1}{8}}={\begin{cases}\;\;\,1&{\text{pokud }}n\equiv 1,7{\pmod {8}}\\-1&{\text{pokud }}n\equiv 3,5{\pmod {8}}\end{cases}}$

Na rozdíl od Legendreova symbolu hodnoty Jacobiho symbolu neodpovídají přesně tomu, zda je a modulo n kvadratickým zbytkem nebo nezbytkem. Platí, že

je-li $\left({\frac {a}{n}}\right)=-1$ , pak $a$ je kvadratický nezbytek ${\pmod {n}}$
je-li $a$ kvadratický zbytek ${\pmod {n}}$ , pak $\left({\frac {a}{n}}\right)=1$ .

Nicméně z toho, že $\left({\frac {a}{n}}\right)=1$ nevyplývá, zda $a$ je nebo není kvadratický zbytek ${\pmod {n}}$ . To je dáno tím, že aby bylo kvadratický zbytek, musí být kvadratickým zbytkem pro všechna prvočísla prvočíselného rozkladu n. Jacobiho symbol se ovšem bude rovnat jedné i v případě, kdy bude a nezbytkem pro sudý počet zmíněných prvočísel.

Efektivní výpočet

Na základě vlastností výše lze vypočítat Jacobiho symbol dvou čísel poměrně efektivně způsobem připomínajícím Eukleidův algoritmus.

Nejprve je možné díky 2. vlastnosti změnit horní číslo na číslo menší než dolní číslo. Pak je možné z něj odstranit pomocí 4. vlastnosti násobky dvou a pomocí 8. vlastnosti je vyčíslit. A pak je možné pomocí 6. vlastnosti Jacobiho symbol převrátit a pokračovat znovu stejným postupem.

Takto se budou obě čísla Jacobiho symbolu postupně snižovat, až buď bude horní z nich rovno 1 (a pak aplikujeme 4. vlastnost) nebo 2 (pak aplikujeme 8. vlastnost), nebo budou čísla shodná (a pak aplikujeme 3. vlastnost).

Srovnání s výpočtem Legendreova symbolu

Přestože je Jacobiho symbol obecnější než Legendreův (a má složitější definici), jeho vlastnosti umožňují dosáhnout jeho upravováním výsledku rychleji. Je tedy vhodné ho použít pro výpočet i v případech, kdy n je prvočíslo.

V případě Legendreova symbolu je totiž před převrácením nutné nalézt prvočíselný rozklad horního čísla, což je obecně asymptoticky velmi náročné.