Jacobiho symbol

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

  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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Chtějme spočítat

Výpočet pouze přes Legendreovy symboly[editovat | editovat zdroj]

Výpočet pomocí Jacobiho symbolů[editovat | editovat zdroj]

Testování prvočíselnosti[editovat | editovat zdroj]

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

Další zobecnění[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

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[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]