Kvadratický zbytek - Quadratic residue

v teorie čísel, an celé číslo q se nazývá a kvadratický zbytek modulo n Pokud to je shodný do a perfektní čtverec modulo n; tj. pokud existuje celé číslo X takové, že:

${ displaystyle x ^ {2} equiv q { pmod {n}}.}$

V opačném případě, q se nazývá a kvadratická rezidua modulo n.

Původně abstrakt matematický koncept z oboru teorie čísel známý jako modulární aritmetika, kvadratické zbytky se nyní používají v aplikacích od akustické inženýrství na kryptografie a factoring velkých čísel.

Historie, konvence a základní fakta

Fermat, Euler, Lagrange, Legendre a další teoretici čísel 17. a 18. století založili věty^[1] a vytvořil domněnky^[2] o kvadratických zbytcích, ale první systematické zpracování je § IV z Gauss je Disquisitiones Arithmeticae (1801). Článek 95 zavádí terminologii „kvadratický zbytek“ a „kvadratický zbytek“ a stanoví, že pokud to objasní kontext, lze adjektivum „kvadratický“ vypustit.

Za dané n seznam kvadratických zbytků modulo n lze získat jednoduchým čtvercem čísel 0, 1, ..., n − 1. Protože A² ≡ (n − A)² (mod n), seznam čtverců modulo n je symetrický kolem n/ 2, a seznam musí jít jen tak vysoko. To je vidět v tabulce níže.

Tedy počet kvadratických zbytků modulo n nemůže překročit n/2 + 1 (n sudý) nebo (n + 1)/2 (n zvláštní).^[3]

Produkt dvou zbytků je vždy zbytkem.

Prime modul

Modulo 2, každé celé číslo je kvadratickým zbytkem.

Modulo zvláštní prvočíslo str existují (str + 1) / 2 zbytky (včetně 0) a (str - 1) / 2 zbytky, o Eulerovo kritérium. V tomto případě je obvyklé považovat 0 za speciální případ a pracovat v rámci multiplikativní skupina nenulových prvků z pole Z /strZ. (Jinými slovy, každá třída shody kromě nulové modulo str má multiplikativní inverzi. To neplatí pro složené moduly.)^[4]

V návaznosti na tuto konvenci je multiplikativní inverzní hodnota zbytku zbytková a inverzní hodnota rezidua je reziduum.^[5]

V návaznosti na tuto konvenci, modulo lichého prvočísla existuje stejný počet zbytků a zbytků.^[4]

Modulo prime, produkt dvou neresiduí je zbytek a produkt neresiduí a (nenulový) zbytek je reziduum.^[5]

První doplněk^[6] do zákon kvadratické vzájemnosti je to pokud str ≡ 1 (mod 4) pak −1 je kvadratický zbytek modulo str, a pokud str ≡ 3 (mod 4) pak −1 je nerezidentní modulo str. To znamená následující:

Li str ≡ 1 (mod 4) zápor rezidua modulo str je reziduum a negativ rezidua je reziduum.

Li str ≡ 3 (mod 4) zápor rezidua modulo str je reziduum a negativ rezidua je zbytek.

Prime power modulus

Všechny liché čtverce jsou ≡ 1 (mod 8) a tedy také ≡ 1 (mod 4). Li A je liché číslo a m = 8, 16 nebo nějaká vyšší síla 2, tedy A je zbytek modulo m kdyby a jen kdyby A ≡ 1 (mod 8).^[7]

Například mod (32) jsou liché čtverce

1² ≡ 15² ≡ 1

3² ≡ 13² ≡ 9

5² ≡ 11² ≡ 25

7² ≡ 9² ≡ 49 ≡ 17

a ty sudé jsou

0² ≡ 8² ≡ 16² ≡ 0

2² ≡ 6²≡ 10² ≡ 14²≡ 4

4² ≡ 12² ≡ 16.

Nenulové číslo je tedy reziduální mod 8, 16 atd., Pokud a pouze v případě, že má formu 4^k(8n + 1).

Číslo A relativně prime k lichému prime str je zbytek modulo jakékoli síly str právě když je to zbytek modulo str.^[8]

Pokud je modul strⁿ,

pak str^kA

je zbytek modulo strⁿ -li k ≥ n

je nerezidentní modulo strⁿ -li k < n je zvláštní

je zbytek modulo strⁿ -li k < n je sudé a A je zbytek

je nerezidentní modulo strⁿ -li k < n je sudé a A není zbytkem.^[9]

Všimněte si, že pravidla se liší pro mocniny dvou a mocniny lichých prvočísel.

Modulo lichý primární výkon n = str^k, produkty zbytků a reziduí relativně připraveny k str řídit se stejnými pravidly jako mod str; str je reziduum a obecně všechny zbytky a rezidua dodržují stejná pravidla, kromě toho, že produkty budou nulové, pokud bude výkon str ve výrobku ≥ n.

Modulo 8, produkt zbytků 3 a 5 je zbytkem 7, a podobně pro permutace 3, 5 a 7. Ve skutečnosti multiplikativní skupina zbytků a 1 tvoří Kleinova čtyřčlenná skupina.

Kompozitní modul není primární síla

Základní skutečnost v tomto případě je

-li A je zbytek modulo n, pak A je zbytek modulo str^k pro každý rozdělení hlavního výkonu n.

-li A je nerezidentní modulo n, pak A je nerezidentní modulo str^k pro aspoň jeden rozdělení hlavního výkonu n.

Modulo složené číslo, produkt dvou zbytků je zbytek. Produktem zbytku a zbytku mohou být zbytky, zbytky nebo nula.

Například z tabulky pro modul 6 1, 2, 3, 4, 5 (zbytky v tučně).

Produktem zbytku 3 a zbytku 5 je zbytek 3, zatímco produkt zbytku 4 a zbytku 2 je zbytkem 2.

Produktem dvou nereziduí může být také zbytek, reziduum nebo nula.

Například z tabulky pro modul 15 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 (zbytky v tučně).

Produktem zbytků 2 a 8 je zbytek 1, zatímco produktem zbytků 2 a 7 je zbytek 14.

Tento jev lze nejlépe popsat pomocí slovníku abstraktní algebry. Třídy shody relativně prime k modulu jsou a skupina při násobení se nazývá skupina jednotek z prsten Z /nZa čtverce jsou a podskupina toho. Různé zbytky mohou patřit různým kosety, a neexistuje žádné jednoduché pravidlo, které předpovídá, ve kterém z nich bude jejich produkt. Modulo a prime, existuje pouze podskupina čtverců a jediný coset.

Skutečnost, že např. Modulo 15 produkt zbytků 3 a 5 nebo zbytku 5 a zbytku 9 nebo dvou zbytků 9 a 10 je nula, pochází z práce v celém kruhu Z /nZ, který má nulové dělitele pro kompozitní n.

Z tohoto důvodu někteří autoři^[10] přidat k definici, že kvadratický zbytek A musí být nejen čtverec, ale také musí být relativně prime do modulu n. (A je coprime n kdyby a jen kdyby A² je coprime n.)

Ačkoli to dělá věci pořádněji, tento článek netrvá na tom, že zbytky musí být coprime k modulu.

Zápisy

Gauss^[11] použitý R a N k označení rezidua a non-rezidua;

například, 2 R 7 a 5 N 7nebo 1 R 8 a 3 N 8.

Ačkoli je tento zápis kompaktní a pro některé účely vhodný,^[12][13] užitečnější notace je Legendární symbol, také nazývaný kvadratický charakter, který je definován pro všechna celá čísla A a pozitivní liché prvočísla str tak jako

${ displaystyle left ({ frac {a} {p}} right) = { begin {cases} ; ; , 0 & { text {if}} p { text {divides}} a +1 & { text {if}} a operatorname {R} p { text {and}} p { text {nerozdělí}} a - 1 & { text {if}} a operatorname { N} p { text {a}} p { text {nerozděluje}} a end {případy}}}$

Existují dva důvody, proč čísla ≡ 0 (mod str) jsou ošetřeny speciálně. Jak jsme viděli, usnadňuje formulaci mnoha vzorců a vět. Druhým (souvisejícím) důvodem je, že kvadratický znak je a homomorfismus z multiplikativní skupina nenulových tříd kongruence modulo str do komplexní čísla pod násobením. Nastavení ${ displaystyle ({ tfrac {np} {p}}) = 0}$ umožňuje jeho doména rozšířit na multiplikativní poloskupina všech celých čísel.^[14]

Jednou výhodou této notace oproti Gaussově je, že symbol Legendre je funkce, kterou lze použít ve vzorcích.^[15] Lze jej také snadno zobecnit na krychlový, kvartální a vyšší zbytky energie.^[16]

Existuje symbol generátoru Legendre pro složené hodnoty str, Jacobi symbol, ale jeho vlastnosti nejsou tak jednoduché: pokud m je složený a symbol Jacobi ${ displaystyle ({ tfrac {a} {m}}) = - 1,}$ pak A N m, a pokud A R m pak ${ displaystyle ({ tfrac {a} {m}}) = 1,}$ ale pokud ${ displaystyle ({ tfrac {a} {m}}) = 1}$ nevíme zda A R m nebo A N m. Například: ${ displaystyle ({ tfrac {2} {15}}) = 1}$ a ${ displaystyle ({ tfrac {4} {15}}) = 1}$, ale 2 N 15 a 4 R 15. Li m je hlavní, symboly Jacobi a Legendre souhlasí.

Distribuce kvadratických zbytků

Ačkoli se zdá, že kvadratické zbytky se vyskytují v poměrně náhodném vzoru modulo n, a toto bylo využíváno v takových aplikace tak jako akustika a kryptografie, jejich distribuce také vykazuje některé nápadné zákonitosti.

Použitím Dirichletova věta na prvočísla v aritmetické průběhy, zákon kvadratické vzájemnosti a Čínská věta o zbytku (CRT) je snadné to vidět pro všechny M > 0 existují prvočísla str taková, že čísla 1, 2, ..., M jsou všechny zbytky modulo str.

Například pokud str ≡ 1 (mod 8), (mod 12), (mod 5) a (mod 28), pak podle zákona kvadratické reciprocity 2, 3, 5 a 7 budou všechny zbytky modulo str, a tedy všechna čísla 1–10 budou. CRT říká, že je to stejné jako str ≡ 1 (mod 840) a Dirichletova věta říká, že existuje nekonečné množství prvočísel této formy. 2521 je nejmenší a skutečně 1² ≡ 1, 1046² ≡ 2, 123² ≡ 3, 2² ≡ 4, 643² ≡ 5, 87² ≡ 6, 668² ≡ 7, 429² ≡ 8, 3² ≡ 9 a 529² ≡ 10 (mod 2521).

Dirichletovy vzorce

První z těchto pravidel vychází z Peter Gustav Lejeune Dirichlet práce (ve 30. letech 19. století) na analytický vzorec pro číslo třídy binární kvadratické formy.^[17] Nechat q být prvočíslem, s komplexní proměnnou a definujte a Dirichletova funkce L. tak jako

${ displaystyle L (s) = součet _ {n = 1} ^ { infty} left ({ frac {n} {q}} right) n ^ {- s}.}$

Dirichlet ukázal, že pokud q ≡ 3 (mod 4), pak

${ displaystyle L (1) = - { frac { pi} { sqrt {q}}} součet _ {n = 1} ^ {q-1} { frac {n} {q}} vlevo ({ frac {n} {q}} vpravo)> 0.}$

Proto v tomto případě (prime q ≡ 3 (mod 4)), součet kvadratických zbytků minus součet reziduí v rozsahu 1, 2, ..., q - 1 je záporné číslo.

Například modulo 11,

1, 2, 3, 4, 5, 6, 7, 8, 9, 10 (zbytky v tučně)

1 + 4 + 9 + 5 + 3 = 22, 2 + 6 + 7 + 8 + 10 = 33 a rozdíl je −11.

Ve skutečnosti bude rozdíl vždy lichým násobkem q -li q > 3.^[18] Naproti tomu pro prime q ≡ 1 (mod 4), součet kvadratických reziduí minus součet reziduí v rozsahu 1, 2, ..., q - 1 je nula, z čehož vyplývá, že obě částky jsou stejné ${ displaystyle { frac {q (q-1)} {4}}}$.^{[Citace je zapotřebí ]}

Dirichlet také dokázal, že pro prime q ≡ 3 (mod 4),

${ displaystyle L (1) = { frac { pi} { vlevo (2- vlevo ({ frac {2} {q}} vpravo) vpravo) ! { sqrt {q}}} } sum _ {n = 1} ^ { frac {q-1} {2}} left ({ frac {n} {q}} right)> 0.}$

To znamená, že mezi čísly 1, 2, ..., (je více kvadratických zbytků než neresiduí)q − 1)/2.

Například modulo 11 má čtyři zbytky méně než 6 (jmenovitě 1, 3, 4 a 5), ​​ale pouze jeden zbytek (2).

Zajímavým faktem o těchto dvou větách je, že všechny známé důkazy se spoléhají na analýzu; nikdo nikdy nepublikoval jednoduchý ani přímý důkaz ani jednoho z těchto tvrzení.^[19]

Zákon kvadratické vzájemnosti

Li str a q jsou lichá prvočísla, pak:

((str je kvadratický zbytek mod q) právě tehdy (q je kvadratický zbytek mod str)) tehdy a jen tehdy (alespoň jeden z str a q je shodný s 1 modem 4).

To je:

${ displaystyle left ({ frac {p} {q}} right) left ({ frac {q} {p}} right) = (- 1) ^ {{ frac {p-1} {2}} cdot { frac {q-1} {2}}}}$

kde ${ displaystyle left ({ frac {p} {q}} right)}$ je Legendární symbol.

Tedy pro čísla A a lichá prvočísla str to se nedělí A:

Viz také kvadratická vzájemnost.

Dvojice zbytků a zbytků

Modulo prime str, počet párů n, n + 1 kde n R str a n + 1 R. strnebo n N str a n + 1 R. stratd. jsou téměř stejné. Přesněji,^[20][21] nechat str být lichý prime. Pro i, j = 0, 1 definuje množiny

${ displaystyle A_ {ij} = left {k in {1,2, dots, p-2 }: left ({ frac {k} {p}} right) = (- 1 ) ^ {i} land left ({ frac {k + 1} {p}} right) = (- 1) ^ {j} right },}$

a nechte

${ displaystyle alpha _ {ij} = | A_ {ij} |.}$

To znamená,

α₀₀ je počet zbytků, za kterými následuje zbytek,

α₀₁ je počet reziduí, za kterými následuje reziduum,

α₁₀ je počet neresiduí, za kterými následuje zbytek, a

α₁₁ je počet nerezidentů, za kterými následuje reziduum.

Pak pokud str ≡ 1 (mod 4)

${ displaystyle alpha _ {00} = { frac {p-5} {4}}, ; alpha _ {01} = alpha _ {10} = alpha _ {11} = { frac { p-1} {4}}}$

a pokud str ≡ 3 (mod 4)

${ displaystyle alpha _ {01} = { frac {p + 1} {4}}, ; alpha _ {00} = alpha _ {10} = alpha _ {11} = { frac { p-3} {4}}.}$

Například: (zbytky v tučně)

Modulo 17

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

A₀₀ = {1,8,15},

A₀₁ = {2,4,9,13},

A₁₀ = {3,7,12,14},

A₁₁ = {5,6,10,11}.

Modulo 19

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

A₀₀ = {4,5,6,16},

A₀₁ = {1,7,9,11,17},

A₁₀ = {3,8,10,15},

A₁₁ = {2,12,13,14}.

Gauss (1828)^[22] zavedl tento druh počítání, když dokázal, že pokud str ≡ 1 (mod 4) pak X⁴ ≡ 2 (mod str) lze vyřešit tehdy a jen tehdy, když str = A² + 64 b².

Nerovnost Pólya – Vinogradov

Hodnoty ${ displaystyle ({ tfrac {a} {p}})}$ pro po sobě jdoucí hodnoty A napodobit náhodnou proměnnou jako a flip na mince.^[23] Konkrétně Pólya a Vinogradov dokázal^[24] (nezávisle) v roce 1918, že pro všechny nonprincipal Dirichletova postava χ (n) modulo q a všechna celá čísla M a N,

${ displaystyle left | sum _ {n = M + 1} ^ {M + N} chi (n) right | = O left ({ sqrt {q}} log q right),}$

v velká O notace. Nastavení

${ displaystyle chi (n) = left ({ frac {n} {q}} right),}$

to ukazuje, že počet kvadratických zbytků modulo q v libovolném intervalu délky N je

${ displaystyle { frac {1} {2}} N + O ({ sqrt {q}} log q).}$

Je to jednoduché^[25] dokázat to

${ displaystyle left | sum _ {n = M + 1} ^ {M + N} left ({ frac {n} {q}} right) right | <{ sqrt {q}} přihlásit q.}$

Ve skutečnosti,^[26]

${ displaystyle left | sum _ {n = M + 1} ^ {M + N} left ({ frac {n} {q}} right) right | <{ frac {4} { pi ^ {2}}} { sqrt {q}} log q + 0,41 { sqrt {q}} + 0,61.}$

Montgomery a Vaughan vylepšil to v roce 1977 a ukázal, že pokud zobecněná Riemannova hypotéza je tedy pravda

${ displaystyle left | sum _ {n = M + 1} ^ {M + N} chi (n) right | = O left ({ sqrt {q}} log log q right) .}$

Tento výsledek nelze podstatně zlepšit, protože Schur v roce 1918 to dokázal

${ displaystyle max _ {N} vlevo | sum _ {n = 1} ^ {N} vlevo ({ frac {n} {q}} vpravo) vpravo |> { frac {1} {2 pi}} { sqrt {q}}}$

a Paley v roce 1932 to dokázal

${ displaystyle max _ {N} vlevo | sum _ {n = 1} ^ {N} vlevo ({ frac {d} {n}} vpravo) vpravo |> { frac {1} {7}} { sqrt {d}} log log d}$

pro nekonečně mnoho d > 0.

Nejméně kvadratické zbytky

Nejméně kvadratický zbytek mod str je jasně 1. Otázka velikosti nejméně kvadratického nezbytku n(str) je jemnější, ale vždy je hlavní. Výše uvedená nerovnost Pólya – Vinogradov dává O (√str log str). Nejlepší bezpodmínečný odhad je n(str) ≪ str^θ pro libovolné θ> 1/4√E, získané odhady Burgesse na součet znaků.^[27] Za předpokladu, že Zobecněná Riemannova hypotéza, Ankeny získá n(str) ≪ (log str)².^[28] Linnik ukázal, že počet str méně než X takhle n(str)> X^ε je omezen konstantou v závislosti na ε.^[27]

Nejméně kvadratický režim bez reziduí str pro lichá prvočísla str jsou:

2, 2, 3, 2, 2, 3, 2, 5, 2, 3, 2, 3, 2, 5, 2, 2, 2, 2, 7, 5, 3, 2, 3, 5, 2, 3, 2, 2, 3, 3, 2, 3, 2, 2, 3, 2, 2, 5, 2, 2, 2, 7, 5, 2, 3, 2, 3, 2, 2, 3, 7, 7, 2, 3, 5, 2, 3, 2, 3, 2, 2, 2, 11, 5, 2, 2, 5, 2, 2, 3, 7, 3, 2, 2, .. (sekvence A053760 v OEIS )

Kvadratický přebytek

Nechat str být lichý prime. The kvadratický přebytek E(str) je počet kvadratických zbytků v rozsahu (0,str/ 2) minus číslo v rozsahu (str/2,str) (sekvence.) A178153 v OEIS ). Pro str shodné s 1 mod 4, přebytek je nula, protože −1 je kvadratický zbytek a zbytky jsou symetrické pod r ↔ str−r. Pro str shodný s 3 mod 4, přebytek E je vždy pozitivní.^[29]

Složitost hledání odmocnin

To je, vzhledem k číslu A a modul n, jak je to těžké

1. říct, zda X Řešení X² ≡ A (mod n) existuje
2. za předpokladu, že existuje, vypočítat to?

Zde se ukazuje důležitý rozdíl mezi prime a složenými moduly. Modulo prime str, kvadratický zbytek A má 1 + (A|str) kořeny (tj. nula, pokud A N str, jeden pokud A ≡ 0 (mod str), nebo dva, pokud A R str a gcd (a, str) = 1.)

Obecně, pokud je složený modul n je psán jako součin sil odlišných prvočísel a existují n₁ kořeny modulo první, n₂ mod druhý, ..., bude n₁n₂... kořeny modulo n.

Teoretický způsob, jakým jsou řešení modulo primárních sil, jsou kombinována, aby byla řešení modulo n se nazývá Čínská věta o zbytku; lze jej implementovat efektivním algoritmem.^[30]

Například:

Vyřešte x² ≡ 6 (mod 15).

X² ≡ 6 (mod 3) má jedno řešení, 0; X² ≡ 6 (mod 5) má dvě, 1 a 4.

a existují dvě řešení modulo 15, konkrétně 6 a 9.

Vyřešte x² ≡ 4 (mod 15).

X² ≡ 4 (mod 3) má dvě řešení, 1 a 2; X² ≡ 4 (mod 5) má dva, 2 a 3.

a existují čtyři řešení modulo 15, konkrétně 2, 7, 8 a 13.

Vyřešte x² ≡ 7 (mod 15).

X² ≡ 7 (mod 3) má dvě řešení, 1 a 2; X² ≡ 7 (mod 5) nemá žádná řešení.

a neexistují žádná řešení modulo 15.

Prime nebo primární modul výkonu

Nejprve, pokud je modul n je hlavní Legendární symbol ${ displaystyle left ({ frac {a} {n}} right)}$ může být rychle vypočítané pomocí varianty Euklidův algoritmus^[31] nebo Eulerovo kritérium. Pokud je to -1, neexistuje žádné řešení. Za druhé, za předpokladu, že ${ displaystyle left ({ frac {a} {n}} right) = 1}$, pokud n ≡ 3 (mod 4), Lagrange zjistil, že řešení jsou dána

${ displaystyle x equiv pm ; a ^ {(n + 1) / 4} { pmod {n}},}$

a Legendre našel podobné řešení^[32] -li n ≡ 5 (mod 8):

${ displaystyle x equiv { begin {cases} pm ; a ^ {(n + 3) / 8} { pmod {n}} & { text {if}} a { text {je kvartikum zbytek modulo}} n pm ; a ^ {(n + 3) / 8} 2 ^ {(n-1) / 4} { pmod {n}} & { text {if}} a { text {je kvartický nezbytkový modul}} n end {případy}}}$

Pro nejlepší n ≡ 1 (mod 8), ale není tam žádný známý vzorec. Tonelli^[33] (v roce 1891) a Cipolla^[34] našel efektivní algoritmy, které fungují pro všechny hlavní moduly. Oba algoritmy vyžadují nalezení kvadratického neresiduálního modula na není známý žádný efektivní deterministický algoritmus. Ale od poloviny čísel mezi 1 a n nejsou zbytky, vybírají čísla X náhodně a výpočet symbolu Legendre ${ displaystyle left ({ frac {x} {n}} right)}$ dokud není nalezena rezidua, rychle ji vytvoří. Mírnou variantou tohoto algoritmu je Algoritmus Tonelli – Shanks.

Pokud modul n je hlavní síla n = str^E, řešení lze nalézt modulo str a „povýšen“ na řešení modulo n použitím Henselův lemma nebo Gaussův algoritmus.^[8]

Složený modul

Pokud modul n bylo zapracováno do hlavních mocností, řešení bylo diskutováno výše.

Li n není v souladu s 2 modulo 4 a Symbol Kronecker ${ displaystyle left ({ tfrac {a} {n}} right) = - 1}$ pak neexistuje řešení; -li n je shodný s 2 modulo 4 a ${ displaystyle left ({ tfrac {a} {n / 2}} right) = - 1}$, pak také neexistuje žádné řešení. Li n není shodný s 2 modulo 4 a ${ displaystyle left ({ tfrac {a} {n}} right) = 1}$nebo n je shodný s 2 modulo 4 a ${ displaystyle left ({ tfrac {a} {n / 2}} right) = 1}$, jeden může, ale nemusí být.

Pokud je úplná faktorizace z n není známo a ${ displaystyle left ({ tfrac {a} {n}} right) = 1}$ a n není shodný s 2 modulo 4, nebo n je shodný s 2 modulo 4 a ${ displaystyle left ({ tfrac {a} {n / 2}} right) = 1}$, je známo, že problém je ekvivalentní s celočíselná faktorizace z n (tj. k efektivnímu řešení druhého problému lze použít efektivní řešení jednoho z problémů).

Výše uvedená diskuse naznačuje, jak znát faktory n umožňuje nám efektivně najít kořeny. Řekněme, že existoval efektivní algoritmus pro nalezení druhé odmocniny modulo složeného čísla. Článek shoda čtverců popisuje, jak najít dvě čísla x a y kde X² ≡ y² (mod n) a X ≠ ±y stačí k faktorizaci n efektivně. Vygenerujte náhodné číslo a zaokrouhlete jej modulo na nechte efektivní algoritmus druhé odmocniny najít kořen. Opakujte, dokud nevrátí číslo, které se nerovná číslu, které jsme původně na druhou (nebo jeho záporné modulo) n), pak postupujte podle algoritmu popsaného v kongruenci čtverců. Účinnost factoringového algoritmu závisí na přesných charakteristikách vyhledávače kořenů (např. Vrací všechny kořeny - jen ten nejmenší - náhodný?), Ale bude efektivní.^[35]

Určení, zda A je kvadratický zbytek nebo nerezidentní modulo n (označeno A R n nebo A N n) lze provést efektivně pro prime n výpočtem symbolu Legendre. Avšak pro kompozitní n, toto tvoří kvadratický problém reziduaity, o kterém není známo, že je tvrdý jako faktorizace, ale předpokládá se, že je docela tvrdá.

Na druhou stranu, pokud chceme vědět, zda existuje řešení pro X menší než nějaký daný limit C, tento problém je NP-kompletní;^[36] toto je však fixovatelný parametr problém, kde C je parametr.

Obecně platí, že k určení, zda A je kvadratický zbytek modulo kompozit n, lze použít následující větu:^[37]

Nechat n > 1, a gcd (A,n) = 1. Pak X² ≡ A (mod n) je řešitelný, jen když:

• The Legendární symbol ${ displaystyle left ({ tfrac {a} {p}} right) = 1}$ pro všechny liché dělitele str z n.
• A ≡ 1 (mod 4) -li n je dělitelné 4, ale ne 8; nebo A ≡ 1 (mod 8) -li n je dělitelné 8.

Poznámka: Tato věta v zásadě vyžaduje, aby faktorizace n je známo. Všimněte si také, že pokud gcd (A,n) = m, pak lze kongruenci snížit na A/m ≡ X²/m (mod n/m), ale pak to odstraní problém od kvadratických zbytků (pokud m je čtverec).

Počet kvadratických zbytků

Seznam počtu kvadratických zbytků modulo n, pro n = 1, 2, 3 ..., vypadá takto:

1, 2, 2, 2, 3, 4, 4, 3, 4, 6, 6, 4, 7, 8, 6, 4, 9, 8, 10, 6, 8, 12, 12, 6, 11, 14, 11, 8, 15, 12, 16, 7, 12, 18, 12, 8, 19, 20, 14, 9, 21, 16, 22, 12, 12, 24, 24, 8, 22, 22, ... (sekvence A000224 v OEIS )

Vzorec pro počítání počtu čtverců modulo n je dán Stanglem.^[38]

Aplikace kvadratických reziduí

Akustika

Zvukové difuzory byly založeny na teoreticko-teoretických koncepcích, jako jsou primitivní kořeny a kvadratické zbytky.^[39]

Teorie grafů

Paleyovy grafy jsou husté neorientované grafy, jeden pro každé prvočíslo str ≡ 1 (mod 4), které tvoří nekonečnou rodinu konferenční grafy, které poskytují nekonečnou rodinu symetrický konferenční matice.

Paleyovy digrafy jsou směrované analogy Paleyových grafů, jeden pro každý str ≡ 3 (mod 4), tento výnos antisymetrický konferenční matice.

Konstrukce těchto grafů využívá kvadratické zbytky.

Kryptografie

Skutečnost, že nalezení druhé odmocniny čísla moduluje velký kompozit n je ekvivalentní factoringu (o kterém se obecně věří, že je a těžký problém ) byl použit pro konstrukci kryptografická schémata tak jako Rabinův kryptosystém a lhostejný přenos. The kvadratický problém reziduaity je základem pro Kryptosystém Goldwasser-Micali.

The diskrétní logaritmus je podobný problém, který se také používá v kryptografii.

Testování originality

Eulerovo kritérium je vzorec pro symbol Legendre (A|str) kde str je hlavní. Li str je složený, vzorec může nebo nemusí počítat (A|str) správně. The Solovay-Strassenův test primality zda dané číslo n je primární nebo složený výběr náhodného A a počítá (A|n) pomocí modifikace Euklidova algoritmu,^[40] a také pomocí Eulerova kritéria.^[41] Pokud výsledky nesouhlasí, n je složený; pokud souhlasí, n mohou být kompozitní nebo primární. Pro kompozit n alespoň 1/2 hodnoty A v rozsahu 2, 3, ..., n - 1 se vrátí "n je složený "; pro prime n nikdo nebude. Pokud po použití mnoha různých hodnot A, n nebylo prokázáno, že je složený, nazývá se „pravděpodobný prime ".

The Miller-Rabinov test primality je založen na stejných principech. Existuje jeho deterministická verze, ale důkaz, že funguje, závisí na zobecněná Riemannova hypotéza; výstup z tohoto testu je „n je rozhodně složený "nebo" buď n je primární nebo GRH je nepravdivé ". Pokud se u kompozitu někdy objeví druhý výstup n, pak by GRH byla nepravdivá, což by mělo důsledky prostřednictvím mnoha oborů matematiky.

Faktorizace celého čísla

V § VI Disquisitiones Arithmeticae^[42] Gauss popisuje dva factoringové algoritmy, které používají kvadratické zbytky a zákon kvadratické vzájemnosti.

Několik moderních faktorizačních algoritmů (včetně Dixonův algoritmus, metoda pokračující frakce, kvadratické síto a číslo pole síto ) generovat malé kvadratické zbytky (modulovat počet faktorizovaného čísla) ve snaze najít a shoda čtverců což přinese faktorizaci. Síto s číselným polem je nejrychlejší známý faktorizační algoritmus pro všeobecné účely.

Tabulka kvadratických reziduí

Následující tabulka (sekvence A096008 v OEIS ) uvádí kvadratické zbytky mod 1 až 75 (a červené číslo znamená, že to není coprime n). (Pro kvadratické zbytky coprime do nviz OEIS: A096103, a pro nenulové kvadratické zbytky viz OEIS: A046071.)

Viz také

• Eulerovo kritérium
• Gaussovo lema
• Zolotarevovo lemma
• Součet znaků
• Zákon kvadratické vzájemnosti
• Kvadratický kód zbytku

Poznámky

Reference

The Disquisitiones Arithmeticae byl přeložen z Gaussova Ciceronian latina do Angličtina a Němec. Německé vydání obsahuje všechny jeho práce o teorii čísel: všechny důkazy kvadratické vzájemnosti, určení znaménka Gaussova suma, vyšetřování dvojkvadratická vzájemnost a nepublikované poznámky.

• Gauss, Carl Friedrich; Clarke, Arthur A. (překladatel do angličtiny) (1986), Disquisitiones Arithemeticae (Druhé opravené vydání), New York: Springer, ISBN  0-387-96254-9
• Gauss, Carl Friedrich; Maser, H. (překladatel do němčiny) (1965), Untersuchungen über hohere Arithmetik [Disquisitiones Arithemeticae a další články o teorii čísel] (druhé vydání), New York: Chelsea, ISBN  0-8284-0191-8
• Bach, Eric; Shallit, Jeffrey (1996), Efektivní algoritmy, Algoritmická teorie čísel, Já, Cambridge: MIT Press, ISBN  0-262-02405-5
• Crandall, Richard; Pomerance, Carl (2001), Prvočísla: Výpočetní perspektiva, New York: Springer, ISBN  0-387-94777-9
• Davenport, Harold (2000), Multiplikativní teorie čísel (třetí vydání), New York: Springer, ISBN  0-387-95097-4
• Garey, Michael R.; Johnson, David S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, ISBN  0-7167-1045-5 A7.1: AN1, s. 249.
• Hardy, G. H.; Wright, E. M. (1980), Úvod do teorie čísel (páté vydání), Oxford: Oxford University Press, ISBN  978-0-19-853171-5
• 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
• Manders, Kenneth L .; Adleman, Leonard (1978), "NP- Problémy s úplným rozhodnutím pro binární kvadratiku ", Journal of Computer and System Sciences, 16 (2): 168–184, doi:10.1016/0022-0000(78)90044-2.

externí odkazy

• Weisstein, Eric W. „Kvadratický zbytek“. MathWorld.
• Důkaz nerovnosti Pólya – Vinogradov na PlanetMath.