Cipolla algoritme

Cipollas algoritme er en teknik til at løse en kongruent ligning af formen

x^{2}\equiv n{\pmod {p)),

hvor , så n vil være kvadratet af x , og hvor er et ulige primtal . Her betegner et sidste felt med elementer . Algoritmen er opkaldt efter den italienske matematiker Michele Cipolla , som opdagede metoden i 1907. ${\displaystyle x,n\in \mathbf {F} _{p))$ $s$ $\mathbf {F} _{p}$ $s$ $\{0,1,\dots ,p-1\}$

Algoritme

Indgang:

$s$ , et ulige primtal,
$n\in \mathbf {F} _{p}$ , kvadratet af et tal.

Afslut:

et tal , der tilfredsstiller ligestillingen $x\in \mathbf {F} _{p}$ $x^{2}=n.$

Trin 1. Find et tal , så det ikke er et kvadrat. En algoritme til at finde sådanne tal er ikke kendt, undtagen ved forsøg og fejl . Vi vælger bare et tal og beregner Legendre-symbolet for at sikre, at det opfylder betingelsen. Chancen for at et tilfældigt tal matcher er . Hvis den er stor nok, er denne værdi omtrent lig med [1] . Det forventede antal forsøg på at få et passende a er således 2. $a\in \mathbf {F} _{p}$ $a^{2}-n$ $-en$ $-en$ $(a^{2}-n|p)$ $-en$ $-en$ $(p-1)/2p$ $s$ $1/2$

Trin 2. Få x ved at beregne i feltet . Dette tal x vil være en af rødderne til ligningen $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}$ $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})$ $x^{2}=n.$

Hvis , så holder også. Da p er ulige, så for den fundne løsning x er der altid en anden løsning lig -x . $x^{2}=n$ $(-x)^{2}=n$ $x\neq -x$

Eksempel

( Bemærk : Alle elementer op til andet trin hører til feltet , og alle elementer i andet trin hører til feltet ). Vi leder efter et nummer x sådan $\mathbf {F} _{13}$ $\mathbf {F} _{13^{2))$ $x^{2}=10.$

Før du anvender algoritmen, skal du kontrollere, at tallet faktisk er en firkant i feltet , hvilket betyder, at Legendre-symbolet skal være lig med 1. Du kan kontrollere dette ved hjælp af Euler-kriteriet : . Dette bekræfter, at 10 er et kvadrat, og algoritmen kan anvendes på det. $ti$ $\mathbf {F} _{13}$ $(10|13)$ $(10|13)\equiv 10^{6}\equiv 1{\bmod {1}}3$

Trin 1: Find et tal a , så det ikke er et kvadrat. Som nævnt ovenfor skal du bruge prøve- og fejlmetoden. Lad os vælge et tal , for det vil være lig med 7. Legendre-symbolet er lig med -1, hvilket igen kan opnås ved hjælp af Euler-kriteriet, . Så tallet passer. $a^{2}-n$ $a=2$ $a^{2}-n$ $(7|13)$ $7^{6}=343^{2}\equiv 5^{2}\equiv 25\equiv -1{\bmod {1}}3$ $a=2$
Trin 2: Beregn $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\ højre)^{7}.$

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

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

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

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

Således er en løsning, ligesom Indeed og $x=6$ $x=-6{\bmod {1}}3=(-6+13){\bmod {1}}3=7.$ $\ 6^{2}=36{\bmod {1}}3=10$ $7^{2}=49{\bmod {1}}3=10.$

Bevis

I den første del af beviset bekræfter vi, at det faktisk er et felt. For at lette beregningerne introducerer vi et tal lig med . Selvfølgelig er det ikke en kvadratisk rest, så kvadratroden findes ikke i . Dette kan groft sagt betragtes som en analog til det komplekse tal i . Feltets aritmetik er ret indlysende. Tillæg defineres som $\mathbf {F} _{p^{2}}=\mathbf {F} _{p}({\sqrt {a^{2}-n}})=\{x+y{\sqrt {a^{2}-n}}:x,y\in \mathbf {F} _{p}\}$ $\omega$ ${\sqrt {a^{2}-n))$ $a^{2}-n$ $\mathbf {F} _{p}$ $\omega$

\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

Multiplikation er også defineret på sædvanlig måde. Hvis vi husker det , får vi det $\omega ^{2}=a^{2}-n$

\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}

=\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

Nu skal vi tjekke feltets egenskaber. Lukning under operationerne addition og multiplikation, associativitet , kommutativitet og distributivitet er let at verificere, da feltet ligner feltet for komplekse tal (hvor det tjener som en analog til i ). Det neutrale element ved tilføjelse er eller, mere formelt, hvis , så $\mathbf {F} _{p^{2))$ $\omega$
$0$ $0+0\omega$ $\alpha \in \mathbf {F} _{p^{2))$

\alpha +0=(x+y\omega )+(0+0\omega )=(x+0)+(y+0)\omega =x+y\omega =\alpha

Det neutrale element ved multiplikation er mere præcist : $en$ $1+0\omega$

\alpha \cdot 1=(x+y\omega )(1+0\omega )=\left(x\cdot 1+0\cdot y\left(a^{2}-n\right)\ højre)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha

Det er kun tilbage at kontrollere, at der er inverse elementer under addition og multiplikation. Det er let at se, at det omvendte af tilføjelsen af et tal er det tal , som også er indeholdt i feltet , fordi . For at vise, at ethvert ikke-nul-element har et element inverst i multiplikation, skriver vi repræsentationerne og . Med andre ord, $\mathbf {F} _{p^{2))$ $x+y\omega$ $-xy\omega$ $\mathbf {F} _{p^{2))$ ${\displaystyle -x,-y\in \mathbf {F} _{p))$ $\alfa$ $\alpha =x_{1}+y_{1}\omega$ $\alpha ^{-1}=x_{2}+y_{2}\omega$

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

Vi får to ligninger, og . Vi løser dette system med hensyn til og , vi får $x_{1}x_{2}+y_{1}y_{2}(n^{2}-a)=1$ $x_{1}y_{2}+y_{1}x_{2}=0$ $x_{2}$ $y_2$

x_{2}=-y_{1}^{-1}x_{1}\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2 }y_{1}^{-1}\right)^{-1}

y_{2}=\left(y_{1}\left(n^{2}-a\right)-x_{1}^{2}y_{1}^{-1}\right)^ {-en}

De omvendte elementer i udtrykkene for og eksisterer, fordi de er elementer i feltet . Dette fuldender den første del af beviset. $x_{2}$ $y_2$ $\mathbf {F} _{p}$

I anden del af beviset vil vi vise det for ethvert element . Per definition er ikke et kvadrat i . Så giver Euler-kriteriet $x+y\omega \in \mathbf {F} _{p^{2}}:(x+y\omega )^{p}=xy\omega$ $\omega ^{2}=a^{2}-n$ $\mathbf {F} _{p}$

\omega ^{p-1}=\left(\omega ^{2}\right)^{\frac {p-1}{2}}=-1

Således ,. Dette sammen med Fermats lille sætning (som angiver, at for alle ) og viden om, at i felter med karakteristiske , viser det ønskede resultat $\omega ^{p}=-\omega$ $x^{p}=x$ $x\in \mathbf {F} _{p}$ ${\displaystyle \left(a+b\right)^{p}=a^{p}+b^{p))$

(x+y\omega )^{p}=x^{p}+y^{p}\omega ^{p}=xy\omega

Den tredje og sidste del af beviset viser, at der i sagen . Beregn $x_{0}=\left(a+\omega \right)^{\frac {p+1}{2}}\in \mathbf {F} _{p^{2}}$ ${\displaystyle x_{0}^{2}=n\in \mathbf {F} _{p))$

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

Bemærk at disse beregninger finder sted i , så . Lagranges sætning siger, at et polynomium , der ikke er nul , af grad n har højst n rødder over et felt K. Givet at polynomiet har 2 rødder i , kan der ikke være andre rødder . Det har vist sig, at og er rødder til polynomiet i , Så . [2] $\mathbf {F} _{p^{2))$ $x_{0}\in \mathbf {F} _{p^{2))$ $x^{2}-n$ $\mathbf {F} _{p}$ $\mathbf {F} _{p^{2))$ $x_{0}$ ${\displaystyle -x_{0))$ $x^{2}-n$ $\mathbf {F} _{p^{2))$ ${\displaystyle x_{0},-x_{0}\in \mathbf {F} _{p))$

Hastighed

Efter at have fundet et passende a , er antallet af operationer, som algoritmen kræver, multiplikationer og additioner, hvor m er antallet af cifre i den binære repræsentation af tallet p , og k er antallet af ener i denne repræsentation. For at finde en ved forsøg og fejl er det forventede antal beregninger af Legendre-symbolet 2. Du kan dog være heldig første gang, men det kan tage mere end 2 forsøg. Følgende to ligheder holder i feltet $4m+2k-4$ $4m-2$ $\mathbf {F} _{p^{2))$

(x+y\omega )^{2}=\left(x^{2}+y^{2}\omega ^{2}\right)+\left(\left(x+y\right )^{2}-x^{2}-y^{2}\right)\omega ,

hvor er kendt på forhånd. Denne beregning kræver 4 multiplikationer og 4 additioner. $\omega ^{2}=a^{2}-n$

\left(x+y\omega \right)^{2}\left(c+\omega \right)=\left(cd-b\left(x+d\right)\right)+\left( d^{2}-ved\right)\omega ,

hvor og . Denne operation kræver 6 multiplikationer og 4 additioner. $d=(x+yc)$ $b=ny$

Hvis vi antager, at (i tilfælde af , er direkte beregning meget hurtigere) har det binære udtryk fortegn, hvoraf k er lig med et. For at beregne den th potens af et tal skal den første formel anvendes én gang og den anden én gang. $p\equiv 1{\pmod {4)),$ $p \equiv 3 \pmod 4$ $x\equiv \pm n^{\frac {p+1}{4))$ $(p+1)/2$ $m-1$ $(p+1)/2$ $\left(a+\omega \right)$ $nk-1$ $k-1$

Cipolla-algoritmen er bedre end Tonelli-Shanks-algoritmen , hvis og kun hvis , hvor er den maksimale effekt på 2, der er delelig med [3] . $S(S-1)>8m+20$ $2^{S}$ $p-1$

Noter

↑ Crandall, Pomerance, 2001 , s. 157.
↑ M. Baker Cipollas algoritme til at finde kvadratrødder mod p . Hentet 29. juni 2017. Arkiveret fra originalen 25. marts 2017. (ubestemt)
↑ Gonzalo Tornaria Firkantrødder modulo p (utilgængeligt link)

Litteratur

R. Crandall, C. Pomerance. Primtal: Et beregningsperspektiv . - Springer-Verlag, 2001. - ISBN 0-387-25282-7 .

Links

E. Bach, JO Shallit Algorithmic Number Theory: Effektive algoritmer MIT Press, (1996)

Talteoretiske algoritmer
Enkelthedstest	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
At finde primtal	Iteration over divisorer Sigte af Eratosthenes Atkins si Sigte Sundarama
Faktorisering	Iteration over divisorer Fermat metode p −1 Pollard metode Pollards ρ-algoritme Lehmanns metode Elliptisk kurvemetode (Lenstras algoritme) Dixons algoritme Firkantet sigte
Diskret logaritme	Gelfond-Shanks algoritme Polig-Hellman algoritme Pollards ρ-metode Pollards kængurualgoritme Adlemans algoritme COS algoritme
Finder GCD	Euklids algoritme Avanceret algoritme Binær algoritme
Modulo aritmetik	Montgomerys algoritme Kinesisk restsætning
Multiplikation og division af tal	Karatsuba algoritme Toom-Cook algoritme Schönhage-Strassen algoritme Fuhrer algoritme Harvey-van der Hoeven algoritme Burnickel-Ziegler algoritme
Beregning af kvadratroden	Tonelli-Shanks algoritme Berlekamp-Rabin algoritme