Jacobi symbol - Jacobi symbol - Wikipedia

The Jacobi symbol je zobecněním Legendární symbol. Představil Jacobi v roce 1837,^[1] je teoreticky zajímavý modulární aritmetika a další pobočky teorie čísel, ale jeho hlavní použití je v výpočetní teorie čísel, zvláště testování primality a celočíselná faktorizace; ty jsou zase důležité v kryptografie.

Definice

Pro jakékoli celé číslo A a jakékoli kladné liché celé číslo n, symbol Jacobi (A/n) je definován jako produkt Legendární symboly odpovídající hlavním faktorům n:

${ displaystyle left ({ frac {a} {n}} right) = left ({ frac {a} {p_ {1}}} right) ^ { alpha _ {1}} left ({ frac {a} {p_ {2}}} vpravo) ^ { alpha _ {2}} cdots left ({ frac {a} {p_ {k}}} right) ^ { alfa _ {k}},}$

kde

${ displaystyle n = p_ {1} ^ { alpha _ {1}} p_ {2} ^ { alpha _ {2}} cdots p_ {k} ^ { alpha _ {k}}}$

je hlavní faktorizace n.

Symbol legendy (A/str) je definována pro všechna celá čísla A a všechny liché prvočísla str podle

${ displaystyle left ({ frac {a} {p}} right) = left {{ begin {array} {rl} 0 & { text {if}} a equiv 0 { pmod {p }}, 1 & { text {if}} a not equiv 0 { pmod {p}} { text {a pro celé číslo}} x colon ; a equiv x ^ {2} { pmod {p}}, - 1 & { text {if}} a not equiv 0 { pmod {p}} { text {a takové neexistuje}} x. end {pole}} že jo.}$

Podle běžné konvence pro prázdný produkt (A/1) = 1.

Když je dolním argumentem liché prvočíslo, Jacobiho symbol se rovná symbolu Legendre.

Tabulka hodnot

Následuje tabulka hodnot symbolu Jacobi (k/n) s n ≤ 59, k ≤ 30, n zvláštní.

Vlastnosti

Následující fakta, dokonce i zákony o vzájemnosti, jsou přímými dedukcemi z definice symbolu Jacobi a odpovídajících vlastností symbolu Legendre.^[2]

Symbol Jacobi je definován pouze v případě, že horní argument („čitatel“) je celé číslo a dolní argument („jmenovatel“) je kladné liché celé číslo.

1. Pokud n je (liché) prvočíslo, pak symbol Jacobi (A/n) se rovná (a je psáno stejně) odpovídajícímu symbolu Legendre.

2. Pokud A ≡ b (mod n), pak ${ displaystyle left ({ frac {a} {n}} right) = left ({ frac {b} {n}} right) = left ({ frac {a pm m cdot n} {n}} vpravo)}$

3. ${ displaystyle left ({ frac {a} {n}} right) = { begin {cases} 0 & { text {if}} gcd (a, n) neq 1, pm 1 & { text {if}} gcd (a, n) = 1. end {případy}}}$

Pokud je horní nebo dolní argument pevný, symbol Jacobi je a zcela multiplikativní funkce ve zbývajícím argumentu:

4. ${ displaystyle left ({ frac {ab} {n}} right) = left ({ frac {a} {n}} right) left ({ frac {b} {n}} right), quad { text {so}} left ({ frac {a ^ {2}} {n}} right) = left ({ frac {a} {n}} right) ^ {2} = 1 { text {or}} 0.}$

5. ${ displaystyle left ({ frac {a} {mn}} right) = left ({ frac {a} {m}} right) left ({ frac {a} {n}} right), quad { text {so}} left ({ frac {a} {n ^ {2}}} right) = left ({ frac {a} {n}} right) ^ {2} = 1 { text {or}} 0.}$

The zákon kvadratické vzájemnosti: pokud m a n jsou tedy lichá pozitivní celá čísla coprime

6. ${ displaystyle left ({ frac {m} {n}} right) left ({ frac {n} {m}} right) = (- 1) ^ {{ tfrac {m-1} {2}} cdot { tfrac {n-1} {2}}} = { begin {cases} 1 & { text {if}} n equiv 1 { pmod {4}} { text {nebo }} m equiv 1 { pmod {4}}, - 1 & { text {if}} n equiv m equiv 3 { pmod {4}} end {případy}}}$

a jeho doplňky

7. ${ displaystyle left ({ frac {-1} {n}} right) = (- 1) ^ { tfrac {n-1} {2}} = { begin {cases} 1 & { text { if}} n equiv 1 { pmod {4}}, - 1 & { text {if}} n equiv 3 { pmod {4}}, end {cases}}}$

8. ${ displaystyle left ({ frac {2} {n}} right) = (- 1) ^ { tfrac {n ^ {2} -1} {8}} = { begin {cases} 1 & { text {if}} n equiv 1,7 { pmod {8}}, - 1 & { text {if}} n equiv 3,5 { pmod {8}}. end {cases} }}$

Kombinace vlastnosti 4 a 8 dává:

9. ${ displaystyle left ({ frac {2a} {n}} right) = left ({ frac {2} {n}} right) left ({ frac {a} {n}} right) = { begin {cases} left ({ frac {a} {n}} right) & { text {if}} n equiv 1,7 { pmod {8}}, - left ({ frac {a} {n}} right) & { text {if}} n equiv 3,5 { pmod {8}}. end {cases}}}$

Jako symbol legendy:

• Li (A/n) = -1 pak A je kvadratické neresiduální modulo n.

• Li A je kvadratický zbytek modulo n a gcd (A,n) = 1, tedy (A/n) = 1.

Ale na rozdíl od symbolu Legendre:

Li (A/n) = 1 tedy A může nebo nemusí být kvadratickým zbytkem modulo n.

Je to proto, že pro A být kvadratickým zbytkem modulo n, musí to být kvadratický zbytek modulo každý hlavní faktor n. Symbol Jacobi se však rovná jednomu, pokud například A je non-zbytek modulo přesně dva z hlavních faktorů n.

Ačkoli Jacobiho symbol nemůže být jednotně interpretován ve smyslu čtverců a jiných čtverců, může být jednotně interpretován jako znak permutace Zolotarevovo lemma.

Symbol Jacobi (A/n) je Dirichletova postava do modulu n.

Výpočet symbolu Jacobi

Výše uvedené vzorce vedou k efektivnímu Ó (log A log b)^[3] algoritmus pro výpočet Jacobiho symbolu, analogický k Euklidovský algoritmus pro nalezení gcd dvou čísel. (To by nemělo být překvapující ve světle pravidla 2.)

1. Snižte „čitatele“ a „jmenovatele“ pomocí pravidla 2.
2. Extrahujte libovolný sudý „čitatel“ pomocí pravidla 9.
3. Pokud je „čitatel“ 1, pravidla 3 a 4 dávají výsledek 1. Pokud „čitatel“ a „jmenovatel“ nejsou coprime, pravidlo 3 dává výsledek 0.
4. Jinak jsou „čitatel“ a „jmenovatel“ nyní lichá kladná celá čísla coprime, takže můžeme symbol převrátit pomocí pravidla 6 a poté se vrátit ke kroku 1.

Implementace v Lua

funkce jacobi(n, k)  tvrdit(k > 0 a k % 2 == 1)  n = n % k  t = 1  zatímco n ~= 0 dělat    zatímco n % 2 == 0 dělat      n = n / 2      r = k % 8      -li r == 3 nebo r == 5 pak        t = -t      konec    konec    n, k = k, n    -li n % 4 == 3 a k % 4 == 3 pak      t = -t    konec    n = n % k  konec  -li k == 1 pak    vrátit se t  jiný    vrátit se 0  koneckonec

Příklad výpočtů

Symbol legendy (A/str) je definováno pouze pro lichá prvočísla str. Řídí se stejnými pravidly jako symbol Jacobi (tj. Vzájemnost a doplňkové vzorce pro (−1/str) a (2/str) a multiplikativita „čitatele“.)

Problém: Vzhledem k tomu, že 9907 je prvočíslo, vypočítejte (1001/9907).

Pomocí symbolu Legendre

${ displaystyle { begin {aligned} left ({ frac {1001} {9907}} right) & = left ({ frac {7} {9907}} right) left ({ frac { 11} {9907}} right) left ({ frac {13} {9907}} right). left ({ frac {7} {9907}} right) & = - left ( { frac {9907} {7}} vpravo) = - vlevo ({ frac {2} {7}} vpravo) = - 1. vlevo ({ frac {11} {9907}} right) & = - left ({ frac {9907} {11}} right) = - left ({ frac {7} {11}} right) = left ({ frac {11} {7}} right) = left ({ frac {4} {7}} right) = 1. left ({ frac {13} {9907}} right) & = left ( { frac {9907} {13}} right) = left ({ frac {1} {13}} right) = 1. left ({ frac {1001} {9907}} right ) & = - 1. end {zarovnáno}}}$

Pomocí symbolu Jacobi

${ displaystyle { begin {aligned} 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) & = 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) & = left ({ frac {29} {37}} right) = left ({ frac {37} {29}} right) = left ({ frac {8} {29}} right) = left ({ frac {2} {29}} right) ^ {3} = - 1. end {aligned}}}$

Rozdíl mezi těmito dvěma výpočty spočívá v tom, že když se použije symbol Legendre, musí se „čitatel“ započítat do hlavních sil, než se symbol převrátí. Díky tomu je výpočet pomocí symbolu Legendre výrazně pomalejší než výpočet pomocí symbolu Jacobi, protože neexistuje žádný algoritmus polynomiálního času pro factoringová celá čísla.^[4] To je důvod, proč Jacobi představil tento symbol.

Testování originality

Existuje ještě další způsob, jak se symboly Jacobi a Legendre liší. Pokud Eulerovo kritérium vzorec se používá modulo složené číslo, výsledkem může nebo nemusí být hodnota Jacobiho symbolu a ve skutečnosti nemusí být ani −1 nebo 1. Například

${ displaystyle { begin {aligned} left ({ frac {19} {45}} right) & = 1 && { text {and}} & 19 ^ { frac {45-1} {2}} & equiv 1 { pmod {45}}. vlevo ({ frac {8} {21}} vpravo) & = - 1 && { text {but}} & 8 ^ { frac {21-1} {2}} & equiv 1 { pmod {21}}. left ({ frac {5} {21}} right) & = 1 && { text {but}} & 5 ^ { frac { 21-1} {2}} & equiv 16 { pmod {21}}. End {zarovnáno}}}$

Pokud tedy není známo, zda číslo n je prvočíslo nebo složené, můžeme vybrat náhodné číslo A, vypočítat symbol Jacobi (A/n) a porovnat to s Eulerovým vzorcem; pokud se liší modulo n, pak n je složený; pokud mají stejný zbytek modulo n pro mnoho různých hodnot A, pak n je „pravděpodobně hlavní“.

To je základ pro pravděpodobnostní Test primality Solovay – Strassen a vylepšení, jako je Baityho-PSW test primality a Miller – Rabinův test primality.

Jako nepřímé použití je možné jej použít jako rutinu detekce chyb během provádění Lucas-Lehmerův test primality jejichž zpracování může dokonce i na moderním počítačovém hardwaru trvat týdny Mersennova čísla přes ${ displaystyle { begin {zarovnáno} 2 ^ {82 589 933} -1 konec {zarovnáno}}}$ (největší známý Mersenne prime od prosince 2018). V nominálních případech symbol Jacobi:

${ displaystyle { begin {aligned} left ({ frac {s_ {i} -2} {M_ {p}}} right) & = - 1 & i neq 0 end {aligned}}}$

To platí i pro konečný zbytek ${ displaystyle { begin {aligned} s_ {p-2} end {aligned}}}$ a proto může být použit jako ověření pravděpodobné platnosti. Pokud se však v hardwaru vyskytne chyba, existuje 50% šance, že se výsledek místo toho změní na 0 nebo 1 a nezmění se s následnými podmínkami ${ displaystyle { begin {zarovnáno} s end {zarovnáno}}}$ (pokud nedojde k další chybě a nezmění ji zpět na -1).

Viz také

• Symbol Kronecker, zobecnění Jacobiho symbolu na všechna celá čísla.
• Symbol zbytkové síly, zobecnění symbolu Jacobi na zbytky vyšších sil.

Poznámky

Reference

• Cohen, Henri (1993). Kurz výpočetní algebraické teorie čísel. Berlín: Springer. ISBN  3-540-55640-0.
• Irsko, Kenneth; Rosen, Michael (1990). Klasický úvod do moderní teorie čísel (druhé vydání). New York: Springer. ISBN  0-387-97329-X.
• Lemmermeyer, Franz (2000). Zákony o vzájemnosti: od Eulera po Eisenstein. Berlín: Springer. ISBN  3-540-66957-4.
• Shallit, Jeffrey (Prosinec 1990). „Nejhorší případ tří algoritmů pro výpočet Jacobiho symbolu“. Journal of Symbolic Computation. 10 (6): 593–61. doi:10.1016 / S0747-7171 (08) 80160-5. Technická zpráva o informatice PCS-TR89-140.
• Vallée, Brigitte; Lemée, Charly (říjen 1998). Průměrné analýzy tří algoritmů pro výpočet Jacobiho symbolu (Technická zpráva). CiteSeerX  10.1.1.32.3425.
• Eikenberry, Shawna Meyer; Sorenson, Jonathan P. (říjen 1998). „Efektivní algoritmy pro výpočet Jacobiho symbolu“ (PDF). Journal of Symbolic Computation. 26 (4): 509–523. CiteSeerX  10.1.1.44.2423. doi:10.1006 / jsco.1998.0226.

externí odkazy

• Vypočítejte symbol Jacobi ukazuje kroky výpočtu.