Cipollasův algoritmus - Cipollas algorithm - Wikipedia

v výpočetní teorie čísel, Cipollov algoritmus je technika řešení a shoda formuláře

${ displaystyle x ^ {2} equiv n { pmod {p}},}$

kde ${ displaystyle x, n in mathbf {F} _ {p}}$, tak n je čtverec X, a kde ${ displaystyle p}$ je zvláštní primární. Tady ${ displaystyle mathbf {F} _ {p}}$ označuje konečnou pole s ${ displaystyle p}$ elementy; ${ displaystyle {0,1, tečky, p-1 }}$. The algoritmus je pojmenován po Michele Cipolla, an italština matematik kdo to objevil v roce 1907.

Kromě primárních modulů je Cipollov algoritmus také schopen přijímat druhé odmocniny modulo primární síly.^[1]

Algoritmus

Vstupy:

• ${ displaystyle p}$liché prvočíslo,
• ${ displaystyle n in mathbf {F} _ {p}}$, což je čtverec.

Výstupy:

• ${ displaystyle x in mathbf {F} _ {p}}$, uspokojující ${ displaystyle x ^ {2} = n.}$

Krok 1 je najít ${ displaystyle a in mathbf {F} _ {p}}$ takhle ${ displaystyle a ^ {2} -n}$ není čtverec. Neexistuje žádný známý algoritmus pro nalezení takového ${ displaystyle a}$, kromě pokus omyl metoda. Jednoduše vyberte ${ displaystyle a}$ a výpočtem Legendární symbol ${ displaystyle (a ^ {2} -n | p)}$ je vidět, zda ${ displaystyle a}$ splňuje podmínku. Šance, že náhodný ${ displaystyle a}$ uspokojí je ${ displaystyle (p-1) / 2p}$. S ${ displaystyle p}$ dost velký, to je asi ${ displaystyle 1/2}$.^[2] Proto očekávaný počet pokusů před nalezením vhodného ${ displaystyle a}$ je asi 2.

Krok 2 je výpočet X výpočtem ${ displaystyle x = left (a + { sqrt {a ^ {2} -n}} right) ^ {(p + 1) / 2}}$ v terénu ${ displaystyle mathbf {F} _ {p ^ {2}} = mathbf {F} _ {p} ({ sqrt {a ^ {2} -n}})}$. Tento X bude ten uspokojující ${ displaystyle x ^ {2} = n.}$

Li ${ displaystyle x ^ {2} = n}$, pak ${ displaystyle (-x) ^ {2} = n}$ také drží. A od té doby p je zvláštní, ${ displaystyle x neq -x}$. Takže kdykoli řešení X je nalezeno, vždy existuje druhé řešení, -X.

Příklad

(Poznámka: Všechny prvky před druhým krokem jsou považovány za prvek ${ displaystyle mathbf {F} _ {13}}$ a všechny prvky v kroku dva jsou považovány za prvky ${ displaystyle mathbf {F} _ {13 ^ {2}}}$).

Najít vše X takhle ${ displaystyle x ^ {2} = 10.}$

Před použitím algoritmu je třeba to zkontrolovat ${ displaystyle 10}$ je opravdu čtverec v ${ displaystyle mathbf {F} _ {13}}$. Proto symbol Legendre ${ displaystyle (10 | 13)}$ musí být rovno 1. To lze vypočítat pomocí Eulerovo kritérium; ${ displaystyle (10 | 13) equiv 10 ^ {6} equiv 1 { bmod {1}} 3.}$ To potvrzuje, že 10 je čtverec, a proto lze použít algoritmus.

• Krok 1: Najděte A takhle ${ displaystyle a ^ {2} -n}$ není čtverec. Jak již bylo uvedeno, musí to být provedeno metodou pokusů a omylů. Vybrat ${ displaystyle a = 2}$. Pak ${ displaystyle a ^ {2} -n}$ se stane 7. Symbolem Legendre ${ displaystyle (7 | 13)}$ musí být -1. To lze opět vypočítat pomocí Eulerova kritéria. ${ displaystyle 7 ^ {6} = 343 ^ {2} equiv 5 ^ {2} equiv 25 equiv -1 { bmod {1}} 3.}$ Tak ${ displaystyle a = 2}$ je vhodnou volbou pro A.
• Krok 2: Vypočítat ${ displaystyle x = left (a + { sqrt {a ^ {2} -n}} right) ^ {(p + 1) / 2} = left (2 + { sqrt {-6}} vpravo) ^ {7}.}$

${ displaystyle left (2 + { sqrt {-6}} right) ^ {2} = 4 + 4 { sqrt {-6}} - 6 = -2 + 4 { sqrt {-6}} .}$

${ displaystyle left (2 + { sqrt {-6}} right) ^ {4} = left (-2 + 4 { sqrt {-6}} right) ^ {2} = - 1- 3 { sqrt {-6}}.}$

${ displaystyle left (2 + { sqrt {-6}} right) ^ {6} = left (-2 + 4 { sqrt {-6}} right) left (-1-3 { sqrt {-6}} right) = 9 + 2 { sqrt {-6}}.}$

${ displaystyle left (2 + { sqrt {-6}} right) ^ {7} = left (9 + 2 { sqrt {-6}} right) left (2 + { sqrt { -6}} vpravo) = 6.}$

Tak ${ displaystyle x = 6}$ je také řešení ${ displaystyle x = -6 { bmod {1}} 3 = (- 6 + 13) { bmod {1}} 3 = 7.}$ Vskutku, ${ displaystyle 6 ^ {2} = 36 { bmod {1}} 3 = 10}$ a ${ displaystyle 7 ^ {2} = 49 { bmod {1}} 3 = 10.}$

Důkaz

První částí důkazu je ověření, že ${ displaystyle mathbf {F} _ {p ^ {2}} = mathbf {F} _ {p} ({ sqrt {a ^ {2} -n}}) = {x + y { sqrt {a ^ {2} -n}}: x, y in mathbf {F} _ {p} }}$ je skutečně pole. Kvůli jednoduchosti zápisu ${ displaystyle omega}$ je definován jako ${ displaystyle { sqrt {a ^ {2} -n}}}$. Samozřejmě, ${ displaystyle a ^ {2} -n}$ je kvadratický zbytek, takže neexistuje odmocnina v ${ displaystyle mathbf {F} _ {p}}$. Tento ${ displaystyle omega}$ lze zhruba považovat za analogický komplexnímu číslu i Polní aritmetika je zcela zřejmá. Přidání je definován jako

${ displaystyle left (x_ {1} + y_ {1} omega right) + left (x_ {2} + y_ {2} omega right) = left (x_ {1} + x_ {2 } right) + left (y_ {1} + y_ {2} right) omega}$.

Násobení je také definována jako obvykle. S ohledem na to ${ displaystyle omega ^ {2} = a ^ {2} -n}$, stává se

${ displaystyle left (x_ {1} + y_ {1} omega right) left (x_ {2} + y_ {2} omega right) = x_ {1} x_ {2} + x_ {1 } y_ {2} omega + y_ {1} x_ {2} omega + y_ {1} y_ {2} omega ^ {2} = vlevo (x_ {1} x_ {2} + y_ {1} y_ {2} left (a ^ {2} -n right) right) + left (x_ {1} y_ {2} + y_ {1} x_ {2} right) omega}$.

Nyní je třeba zkontrolovat vlastnosti pole. Vlastnosti uzavření při sčítání a násobení, asociativita, komutativita a distribučnost jsou snadno viditelné. Je to proto, že v tomto případě pole ${ displaystyle mathbf {F} _ {p ^ {2}}}$ je poněkud připomíná pole komplexní čísla (s ${ displaystyle omega}$ je obdobou i).
Přísada identita je ${ displaystyle 0}$, nebo více formálně ${ displaystyle 0 + 0 omega}$: Nechte ${ displaystyle alpha in mathbf {F} _ {p ^ {2}}}$, pak

${ Displaystyle alpha + 0 = (x + y omega) + (0 + 0 omega) = (x + 0) + (y + 0) omega = x + y omega = alfa}$.

Multiplikativní identita je ${ displaystyle 1}$, nebo více formálně ${ displaystyle 1 + 0 omega}$:

${ Displaystyle alpha cdot 1 = (x + y omega) (1 + 0 omega) = levý (x cdot 1 + 0 cdot y levý (a ^ {2} -n pravý) vpravo) + (x cdot 0 + 1 cdot y) omega = x + y omega = alpha}$.

Zbývá jediné ${ displaystyle mathbf {F} _ {p ^ {2}}}$ být polem je existence aditivní a multiplikativní inverze. Je snadno vidět, že aditivní inverzní z ${ displaystyle x + y omega}$ je ${ displaystyle -x-y omega}$, což je prvek ${ displaystyle mathbf {F} _ {p ^ {2}}}$, protože ${ displaystyle -x, -y in mathbf {F} _ {p}}$. Ve skutečnosti jde o aditivní inverzní prvky X a y. Pro zobrazení, že každý nenulový prvek ${ displaystyle alpha}$ má multiplikativní inverzní, zapište ${ displaystyle alpha = x_ {1} + y_ {1} omega}$ a ${ displaystyle alpha ^ {- 1} = x_ {2} + y_ {2} omega}$. Jinými slovy,

${ displaystyle (x_ {1} + y_ {1} omega) (x_ {2} + y_ {2} omega) = left (x_ {1} x_ {2} + y_ {1} y_ {2} left (a ^ {2} -n right) right) + left (x_ {1} y_ {2} + y_ {1} x_ {2} right) omega = 1}$.

Takže dvě rovnosti ${ displaystyle x_ {1} x_ {2} + y_ {1} y_ {2} (a ^ {2} -n) = 1}$ a ${ displaystyle x_ {1} y_ {2} + y_ {1} x_ {2} = 0}$ musí držet. Zpracování podrobností dává výrazy pro ${ displaystyle x_ {2}}$ a ${ displaystyle y_ {2}}$, jmenovitě

${ displaystyle x_ {2} = - y_ {1} ^ {- 1} x_ {1} left (y_ {1} left (a ^ {2} -n right) -x_ {1} ^ {2 } y_ {1} ^ {- 1} vpravo) ^ {- 1}}$,

${ displaystyle y_ {2} = left (y_ {1} left (a ^ {2} -n right) -x_ {1} ^ {2} y_ {1} ^ {- 1} right) ^ {-1}}$.

Inverzní prvky, které jsou zobrazeny ve výrazech ${ displaystyle x_ {2}}$ a ${ displaystyle y_ {2}}$ existují, protože to jsou všechny prvky ${ displaystyle mathbf {F} _ {p}}$. Tím je dokončena první část důkazu, což ukazuje ${ displaystyle mathbf {F} _ {p ^ {2}}}$ je pole.

Druhá a střední část důkazu ukazuje, že pro každý prvek ${ displaystyle x + y omega in mathbf {F} _ {p ^ {2}} :( x + y omega) ^ {p} = x-y omega}$.Podle definice, ${ displaystyle omega ^ {2} = a ^ {2} -n}$ není čtverec v ${ displaystyle mathbf {F} _ {p}}$. Eulerovo kritérium to pak říká

${ displaystyle omega ^ {p-1} = vlevo ( omega ^ {2} doprava) ^ { frac {p-1} {2}} = - 1}$.

Tím pádem ${ displaystyle omega ^ {p} = - omega}$. To spolu s Fermatova malá věta (což říká, že ${ displaystyle x ^ {p} = x}$ pro všechny ${ displaystyle x in mathbf {F} _ {p}}$) a znalosti, které v oborech charakteristický p rovnice ${ displaystyle left (a + b right) ^ {p} = a ^ {p} + b ^ {p}}$ drží, vztah někdy nazývaný První sen, ukazuje požadovaný výsledek

${ displaystyle (x + y omega) ^ {p} = x ^ {p} + y ^ {p} omega ^ {p} = x-y omega}$.

Třetí a poslední částí důkazu je ukázat, že pokud ${ displaystyle x_ {0} = left (a + omega right) ^ { frac {p + 1} {2}} in mathbf {F} _ {p ^ {2}}}$, pak ${ displaystyle x_ {0} ^ {2} = n in mathbf {F} _ {p}}$.
Vypočítat

${ displaystyle x_ {0} ^ {2} = left (a + omega right) ^ {p + 1} = (a + omega) (a + omega) ^ {p} = (a + omega) (a - omega) = a ^ {2} - omega ^ {2} = a ^ {2} - left (a ^ {2} -n right) = n}$.

Všimněte si, že tento výpočet proběhl v ${ displaystyle mathbf {F} _ {p ^ {2}}}$, takže tohle ${ displaystyle x_ {0} in mathbf {F} _ {p ^ {2}}}$. Ale s Lagrangeova věta s tím, že nenulová polynomiální stupně n má nanejvýš n kořeny v jakémkoli oboru K.a znalost toho ${ displaystyle x ^ {2} -n}$ má 2 kořeny v ${ displaystyle mathbf {F} _ {p}}$, tyto kořeny musí být všechny kořeny ${ displaystyle mathbf {F} _ {p ^ {2}}}$. To se právě ukázalo ${ displaystyle x_ {0}}$ a ${ displaystyle -x_ {0}}$ jsou kořeny ${ displaystyle x ^ {2} -n}$ v ${ displaystyle mathbf {F} _ {p ^ {2}}}$, tak to musí být ono ${ displaystyle x_ {0}, - x_ {0} in mathbf {F} _ {p}}$.^[3]

Rychlost

Po nalezení vhodného A, počet operací požadovaných pro algoritmus je ${ displaystyle 4m + 2k-4}$ násobení, ${ displaystyle 4m-2}$ částky, kde m je počet číslice v binární reprezentace z p a k je počet těch v tomto zastoupení. Najít A metodou pokusu a omylu je očekávaný počet výpočtů symbolu Legendre 2. Jeden však může mít štěstí při prvním pokusu a jeden může potřebovat více než 2 pokusy. V oboru ${ displaystyle mathbf {F} _ {p ^ {2}}}$, platí následující dvě rovnosti

${ displaystyle (x + y omega) ^ {2} = vlevo (x ^ {2} + y ^ {2} omega ^ {2} vpravo) + doleva ( vlevo (x + y doprava) ) ^ {2} -x ^ {2} -y ^ {2} vpravo) omega,}$

kde ${ displaystyle omega ^ {2} = a ^ {2} -n}$ je známo předem. Tento výpočet vyžaduje 4 násobení a 4 součty.

${ displaystyle left (x + y omega right) ^ {2} left (a + omega right) = left (ad ^ {2} -b left (x + d right) right) + left (d ^ {2} -by right) omega,}$

kde ${ displaystyle d = (x + ya)}$ a ${ displaystyle b = ny}$. Tato operace vyžaduje 6 násobení a 4 součty.

Za předpokladu, že ${ displaystyle p equiv 1 { pmod {4}},}$ (v případě ${ displaystyle p equiv 3 { pmod {4}}}$, přímý výpočet ${ displaystyle x equiv pm n ^ { frac {p + 1} {4}}}$ je mnohem rychlejší) binární výraz ${ displaystyle (p + 1) / 2}$ má ${ displaystyle m-1}$ číslice, z toho k jsou jedni. Takže pro výpočet a ${ displaystyle (p + 1) / 2}$ síla ${ displaystyle left (a + omega right)}$, je třeba použít první vzorec ${ displaystyle n-k-1}$ časy a druhý ${ displaystyle k-1}$ krát.

Z tohoto důvodu je Cipollov algoritmus lepší než Algoritmus Tonelli – Shanks kdyby a jen kdyby ${ displaystyle S (S-1)> 8m + 20}$, s ${ displaystyle 2 ^ {S}}$ je maximální výkon 2, který rozděluje ${ displaystyle p-1}$.^[4]

Prime power modui

Podle Dicksonovy „Historie čísel“ najde následující vzorec Cipolly druhou mocninu modulo mocnin prvočísla:^[5][6]

${ displaystyle 2 ^ {- 1} q ^ {t} ((k + { sqrt {k ^ {2} -q}}) ^ {s} + (k - { sqrt {k ^ {2} -q }}) ^ {s}) { bmod {p ^ { lambda}}}}$

kde ${ displaystyle t = (p ^ { lambda} -2p ^ { lambda -1} +1) / 2}$ a ${ displaystyle s = p ^ { lambda -1} (p + 1) / 2}$

kde ${ displaystyle q = 10}$, ${ displaystyle k = 2}$ jako v příkladu tohoto článku

Vezmeme-li příklad v článku wiki, můžeme vidět, že tento vzorec výše skutečně přijímá druhé odmocniny modulo prime power.

Tak jako

${ displaystyle { sqrt {10}} { bmod {13 ^ {3}}} ekv 1046}$

Nyní vyřešte pro ${ displaystyle 2 ^ {- 1} q ^ {t}}$ přes:

${ displaystyle 2 ^ {- 1} 10 ^ {(13 ^ {3} -2 cdot 13 ^ {2} +1) / 2} { bmod {13 ^ {3}}} ekv 1086}$

Nyní vytvořte ${ displaystyle (2 + { sqrt {2 ^ {2} -10}}) ^ {13 ^ {2} cdot 7} { bmod {13 ^ {3}}}}$ a ${ displaystyle (2 - { sqrt {2 ^ {2} -10}}) ^ {13 ^ {2} cdot 7} { bmod {13 ^ {3}}}}$(Vidět tady pro matematický kód zobrazující výše uvedený výpočet, pamatující si, že se zde děje něco blízkého složité modulární aritmetice)

Jako takový:

${ displaystyle (2 + { sqrt {2 ^ {2} -10}}) ^ {13 ^ {2} cdot 7} { bmod {13 ^ {3}}} ekv 1540}$ a ${ displaystyle (2 - { sqrt {2 ^ {2} -10}}) ^ {13 ^ {2} cdot 7} { bmod {13 ^ {3}}} ekv 1540}$

a konečná rovnice je:

${ displaystyle 1086 (1540 + 1540) { bmod {13 ^ {3}}} ekv 1046}$ což je odpověď.

Reference

Zdroje

• E. Bach, J.O. Shallit Algoritmická teorie čísel: Efektivní algoritmy MIT Press, (1996)
• Leonard Eugene Dickson Dějiny teorie čísel Svazek 1 p218 ^[1]