Jacobiho symbol

Carl Gustav Jacob Jacobi (1804–1851): pruský matematik, profesor matematiky na Königsberské univerzitě.

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:

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

Vlastnosti

  1. Je-li n liché prvočíslo pak se Jacobiho symbol rovná Legendreovu symbolu.
  2. Pokud platí , pak také platí
  3. Pokud jsou čísla a, n soudělná, je Jacobiho symbol roven 0, jinak nabývá jedné z hodnot +1, −1.
  4. , tedy (případně )
  5. , tedy (případně )
  6. zákon kvadratické reciprocity: Pokud jsou m a n lichá nesoudělná přirozená čísla, pak

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 , pak je kvadratický nezbytek
  • je-li kvadratický zbytek , pak .

Nicméně z toho, že nevyplývá, zda je nebo není kvadratický zbytek . 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é.

Příklad výpočtu

Chtějme spočítat

Výpočet pouze přes Legendreovy symboly

Výpočet pomocí Jacobiho symbolů

Testování prvočíselnosti

Jacobiho symbol lze použít k testování prvočíselnosti pomocí Eulerova kritéria.

Další zobecnění

V oboru celých čísel lze princip Legendreova symbolu dále rozšířit na Kroneckerův symbol.

Také lze definovat Jacobiho symbol i v jiných oborech než v celých číslech, například pro algebraická celá čísla.[1]

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Jacobi symbol na anglické Wikipedii.

  1. FADDĚJEV, Dmitrij Konstantinovič. O devátém Hilbertově problému. Pokroky matematiky, fyziky a astronomie. 1973, roč. 18, čís. 2, s. 90–96. Dostupné online. 

Literatura

Externí odkazy

Média použitá na této stránce

Carl Jacobi.jpg
Carl Gustav Jacob Jacobi was not only a great German mathematician but also considered by many as the most inspiring teacher of his time.