Cipolla algoritm

Cipollas algoritm är en teknik för att lösa en kongruent formekvation

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

där , så n blir kvadraten av x , och där är ett udda primtal . Här betecknar ett sista fält med element . Algoritmen är uppkallad efter den italienske matematikern Michele Cipolla , som upptäckte metoden 1907. ${\displaystyle x,n\in \mathbf {F} _{p))$ $sid$ $\mathbf {F} _{p}$ $sid$ $\{0,1,\dots ,p-1\}$

Algoritm

Ingång:

$sid$ , ett udda primtal,
$n\in \mathbf {F} _{p}$ , kvadraten på ett tal.

Utgång:

ett tal som uppfyller jämställdheten $x\in \mathbf {F} _{p}$ $x^{2}=n.$

Steg 1. Hitta ett tal så att det inte är en kvadrat. En algoritm för att hitta sådana siffror är inte känd, förutom genom försök och misstag . Vi väljer bara ett tal och beräknar Legendre-symbolen för att säkerställa att den uppfyller villkoret. Chansen att ett slumptal matchar är . Om det är tillräckligt stort är detta värde ungefär lika med [1] . Det förväntade antalet försök att få ett lämpligt a är alltså 2. $a\in \mathbf {F} _{p}$ $a^{2}-n$ $a$ $a$ $(a^{2}-n|p)$ $a$ $a$ $(p-1)/2p$ $sid$ $1/2$

Steg 2. Få x genom att räkna i fältet . Detta tal x kommer att vara en av rötterna till ekvationen $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.$

Om , då gäller också. Eftersom p är udda, så för den hittade lösningen x finns det alltid en andra lösning lika med -x . $x^{2}=n$ $(-x)^{2}=n$ $x\neq -x$

Exempel

( Obs : Alla element upp till det andra steget tillhör fältet och alla element i det andra steget tillhör fältet ). Vi letar efter ett antal x sådana att $\mathbf {F} _{13}$ $\mathbf {F} _{13^{2))$ $x^{2}=10.$

Innan du tillämpar algoritmen måste du kontrollera att talet faktiskt är en kvadrat i fältet , vilket betyder att Legendre-symbolen måste vara lika med 1. Du kan kontrollera detta med Euler-kriteriet : . Detta bekräftar att 10 är en kvadrat och algoritmen kan appliceras på den. $tio$ $\mathbf {F} _{13}$ $(10|13)$ $(10|13)\equiv 10^{6}\equiv 1{\bmod {1}}3$

Steg 1: Hitta ett tal a så att det inte är en kvadrat. Som nämnts ovan måste du använda trial and error-metoden. Låt oss välja ett tal , för det kommer att vara lika med 7. Legendre-symbolen är lika med -1, vilket återigen kan erhållas med Euler-kriteriet, . Så numret stämmer. $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$
Steg 2: Beräkna $x=\left(a+{\sqrt {a^{2}-n}}\right)^{(p+1)/2}=\left(2+{\sqrt {-6}}\ höger)^{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 är en lösning, liksom Indeed and $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örsta delen av beviset verifierar vi att det verkligen är ett fält. För att förenkla beräkningarna introducerar vi ett tal lika med . Naturligtvis är inte en kvadratisk rest, så kvadratroten finns inte i . Detta kan, grovt sett, betraktas som en analog till det komplexa talet i . Aritmetiken för fältet är ganska uppenbar. Tillägg definieras 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 definieras också på vanligt sätt. Kommer vi ihåg det så 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 måste vi kontrollera fältets egenskaper. Stängning under operationerna addition och multiplikation, associativitet , kommutativitet och distributivitet är lätt att verifiera, eftersom fältet liknar fältet för komplexa tal (där det fungerar som en analog till i ). Det neutrala elementet genom addition är eller, mer formellt, om , då $\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 neutrala elementet genom multiplikation är , mer exakt : $ett$ $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öger)+(x\cdot 0+1\cdot y)\omega =x+y\omega =\alpha

Det återstår bara att kontrollera att det finns inversa element under addition och multiplikation. Det är lätt att se att inversen av tillägget av ett tal är talet , som också finns i fältet , eftersom . För att visa att alla element som inte är noll har ett element inverst i multiplikation, skriver vi ut representationerna och . Med andra 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 två ekvationer, och . Vi löser detta system med avseende på och , 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)^ {-ett}

De omvända elementen i uttrycken för och existerar eftersom de är element i fältet . Detta avslutar den första delen av beviset. $x_{2}$ $y_2$ $\mathbf {F} _{p}$

I den andra delen av beviset kommer vi att visa det för alla element . Per definition är inte en kvadrat i . Då ger Eulerkriteriet $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

Alltså ,. Detta, tillsammans med Fermats lilla sats (som anger att för alla ) och kunskapen om att i fält med karakteristisk , visar det önskade resultatet $\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 och sista delen av bevisningen visar att i målet . Beräkna $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

Observera att dessa beräkningar sker i , så . Lagranges teorem säger att ett polynom som inte är noll av grad n har högst n rötter över ett fält K. Med tanke på att polynomet har 2 rötter i , kan det inte finnas några andra rötter . Det har visat sig att och är rötter till polynomet 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))$

Hastighet

Efter att ha hittat ett lämpligt a är antalet operationer som krävs av algoritmen multiplikationer och additioner, där m är antalet siffror i den binära representationen av talet p och k är antalet ettor i denna representation. För att hitta en genom försök och misstag är det förväntade antalet beräkningar av Legendre-symbolen 2. Du kan dock ha tur första gången, men det kan ta mer än 2 försök. Följande två likheter gäller i fältet $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 ,

var är känt i förväg. Denna beräkning kräver 4 multiplikationer och 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}-av\höger)\omega ,

var och . Denna operation kräver 6 multiplikationer och 4 additioner. $d=(x+yc)$ $b=ny$

Om vi antar att (i fallet med , är direkt beräkning mycket snabbare) det binära uttrycket har tecken, varav k är lika med ett. För att beräkna potensen av ett tal måste den första formeln användas en gång och den andra en gång. $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 är bättre än Tonelli-Shanks-algoritmen om och bara om , där är den maximala effekten av 2 som är delbar med [3] . $S(S-1)>8m+20$ $2^{S}$ $p-1$

Anteckningar

↑ Crandall, Pomerance, 2001 , sid. 157.
↑ M. Baker Cipollas algoritm för att hitta kvadratrötter mod p . Hämtad 29 juni 2017. Arkiverad från originalet 25 mars 2017. (obestämd)
↑ Gonzalo Tornaria Kvadratrötter modulo p (otillgänglig länk)

Litteratur

R. Crandall, C. Pomerance. Prime Numbers: A Computational Perspective . - Springer-Verlag, 2001. - ISBN 0-387-25282-7 .

Länkar

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

Talteoretiska algoritmer
Enkelhetstest	Mjölnare Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Sachsen Nightingale - Strassen
Hitta primtal	Itererar över divisorer Sil av Eratosthenes Atkins såll Sikt Sundarama
Faktorisering	Itererar över divisorer Fermat-metoden p −1 Pollardmetoden Pollards ρ-algoritm Lehmanns metod Elliptisk kurvmetod (Lenstras algoritm) Dixons algoritm Fyrkantig sil
Diskret logaritm	Gelfond-Shanks algoritm Polig-Hellman algoritm Pollards ρ-metod Pollards kängurualgoritm Adlemans algoritm COS-algoritm
Hitta GCD	Euklids algoritm Avancerad algoritm Binär algoritm
Modulo aritmetik	Montgomerys algoritm Kinesisk restsats
Multiplikation och division av tal	Karatsuba algoritm Toom-Cook algoritm Schönhage-Strassen algoritm Fuhrer algoritm Harvey-van der Hoevens algoritm Burnickel-Ziegler algoritm
Beräkna kvadratroten	Tonelli-Shanks algoritm Berlekamp-Rabin algoritm