Algoritmul lui Shuf

Algoritmul lui Schuf este un algoritm eficient [1] pentru numărarea numărului de puncte de pe o curbă eliptică peste un câmp finit . Algoritmul are aplicații în criptografia eliptică , unde este important să se cunoască numărul de puncte pentru a judeca dificultatea rezolvării unei probleme de logaritm discret pe un grup de puncte pe o curbă eliptică.

Algoritmul a fost publicat în 1985 de René Chouf și a fost o descoperire teoretică, deoarece a fost primul algoritm determinist de timp polinomial pentru numărarea punctelor pe o curbă eliptică . Înainte de algoritmul lui Schuf, abordările de numărare a punctelor pe curbele eliptice, cum ar fi algoritmul simplu de pași mici și mari , erau în cea mai mare parte laborioase și necesitau timp de rulare exponențial.

Acest articol explică abordarea lui Schuf, concentrându-se pe ideile matematice din spatele algoritmului.

Introducere

Fie o curbă eliptică definită pe un câmp finit , unde pentru prim și întreg . Peste un câmp cu caracteristică o curbă eliptică poate fi dată (pe scurt) de ecuația Weierstrass $E$ $\mathbb {F} _{q}$ $q=p^{n}$ $p$ $n\geq 1$ $\neq 2,3$

y^{2}=x^{3}+Ax+B

cu . Mulțimea punctelor definite peste este formată din soluții care satisfac ecuația curbei și punctul de la infinit . Dacă se folosește legea grupului pe curbele eliptice pe această mulțime, se poate observa că această mulțime formează un grup abelian , în care acționează ca element zero. Pentru a număra punctele pe o curbă eliptică, calculăm cardinalitatea mulțimii . Abordarea Schuf folosește teorema curbei eliptice a lui Hasse , împreună cu teorema chineză a restului și polinoamele de diviziune pentru a calcula cardinalitatea . $A,B\in \mathbb {F} _{q)$ $\mathbb {F} _{q}$ $(a,b)\in \mathbb {F} _{q}^{2}$ $O$ $E(\mathbb {F} _{q})$ $O$ $E(\mathbb {F} _{q})$ $\sharp E(\mathbb {F} _{q})$

Teorema lui Hasse

Teorema lui Hasse afirmă că dacă este o curbă eliptică peste un câmp finit, atunci satisface inegalitatea $E/\mathbb {F} _{q)$ $\mathbb {F} _{q}$ $\sharp E(\mathbb {F} _{q})$

\mid q+1-\sharp E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q)).

Acest rezultat puternic, obținut de Hasse în 1934, ne simplifică sarcina prin restrângerea la un set finit (deși mare) de posibilități. Dacă determinăm cum și folosim acest rezultat, obținem că calculul puterii modulo , unde , este suficient pentru a calcula , și deci pentru a obține . Deși nu există o modalitate eficientă de a calcula direct pentru numerele generale, este posibil să se calculeze pentru un prim mic destul de eficient. Alegem ca un set de numere prime diferite, astfel încât . Dacă este dată pentru toate , teorema chineză a restului vă permite să calculați . $\sharp E(\mathbb {F} _{q})$ $t$ $q+1-\sharp E(\mathbb {F} _{q})$ $t$ $N$ $N>4{\sqrt {q)}$ $t$ $\sharp E(\mathbb {F} _{q})$ $t{\pmod {N}}$ $N$ $t{\pmod {l}}$ $l$ $S=\{l_{1},l_{2},...,l_{r))\}$ $\prod l_{i}=N>4{\sqrt {q}}$ $t{\pmod {l_{i)}}$ $l_{i}\în S$ $t{\pmod {N}}$

Pentru a calcula pentru primul , folosim teoria endomorfismului Frobenius și polinoamele de diviziune . Rețineți că luarea în considerare a numerelor prime nu duce la probleme, deoarece putem alege întotdeauna un număr prim mai mare pentru a ne asigura că produsul este suficient de mare. În orice caz, algoritmul Schuf este cel mai des folosit pentru cazul , deoarece există algoritmi mai eficienți, așa-numiți -adici, pentru câmpuri cu caracteristică mică. $t{\pmod {l}}$ $l\neq p$ $\phi$ $l\neq p$ $q=p$ $p$

Endomorfismul Frobenius

Având în vedere o curbă eliptică definită peste , considerăm punctele peste , închiderea algebrică a câmpului . Adică, permitem punctelor să aibă coordonate în . Endomorfismul Frobenius se extinde pe o curbă eliptică cu o mapare . $E$ $\mathbb {F} _{q}$ $E$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ ${\bar {\mathbb {F} }}_{q}$ ${\bar {\mathbb {F} }}_{q}$ $\mathbb {F} _{q}$ $\phi :(x,y)\mapsto (x^{q},y^{q})$

Această hartă este identică și poate fi extinsă cu un punct până la infinit , făcându-l un morfism de grup de la sine. $E(\mathbb {F} _{q})$ $O$ $E({\bar {\mathbb {F} _{q))})$

Endomorfismul Frobenius satisface o ecuație pătratică legată de putere prin următoarea teoremă: $E(\mathbb {F} _{q})$

Teorema: Endomorfismul Frobenius dat de mapare satisface ecuația caracteristică $\phi$

\phi ^{2}-t\phi +q=0

, Unde

t=q+1-\sharp E(\mathbb {F} _{q})

Atunci pentru tot ce avem , unde + înseamnă adăugarea unei curbe eliptice și și înseamnă produsul scalar al unui punct pe și un punct pe [2] . $P=(x,y)\in E$ $(x^{q^{2}},y^{q^{2}})+q(x,y)=t(x^{q},y^{q})$ $q(x,y)$ $t(x^{q},y^{q})$ $(X y)$ $q$ $(x^{q},y^{q})$ $t$

Puteți încerca să calculați aceste puncte sub formă simbolică și ca funcții pe inelul de coordonate de pe curbă și apoi căutați o valoare care satisface ecuația. Cu toate acestea, gradele se dovedesc a fi foarte mari și această abordare nu are valoare practică. $(x^{q^{2}},y^{q^{2}})$ $(x^{q},y^{q})$ $q(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B)$ $E$ $t$

Ideea lui Schuf a fost să efectueze astfel de calcule, limitându-se la punctele de ordine pentru diverse numere prime mici . Fixând un număr prim impar, se trece la rezolvarea problemei determinării , definită ca , pentru un prim dat . Dacă punctul se află în subgrupul -torsion al lui , atunci , unde este singurul întreg astfel încât și . Rețineți că și că pentru orice număr întreg avem . Astfel, are aceeași ordine ca . Atunci pentru , care aparține de , avem și dacă . În consecință, ne-am redus problema la rezolvarea ecuației $l$ $l$ $l$ $t_{l)$ $t{\pmod {l}}$ $l\neq 2,p$ $(X y)$ $l$ $E[l]=\{P\in E({\bar {\mathbb {F} _{q)}})\mid lP=O\)$ $qP={\bar {q}}P$ ${\bar {q)}$ $q\equiv {\bar {q}}{\pmod {l}}$ $\mid {\bar {q}}\mid <l/2$ $\phi (O)=O$ $r$ $r\phi (P)=\phi (rP)$ $\phi (P)$ $P$ $(X y)$ $E[l]$ $t(x^{q},y^{q})={\bar {t))(x^{q},y^{q})$ $t\equiv {\bar {t}}{\pmod {l}}$

(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)\equiv {\bar {t}}(x^{ q},y^{q}),

unde si zace in interval . ${\bar {t)}$ ${\bar {q)}$ $[-(l-1)/2,(l-1)/2]$

Calcule modulo

Polinomul de diviziune cu indicele l este un polinom astfel încât rădăcinile sale sunt exact coordonatele x ale punctelor de ordin l . Atunci restrângerea calcululuila punctele l -torsiune înseamnă calculul acestor expresii în funcție de inelul de coordonate E și modululpolinomului de l -a diviziune . Adică lucrăm în. Aceasta înseamnă, în special, că gradul de X și Y definit denu depășește 1 față de variabila y șifață de variabila x . $(x^{q^{2}},y^{q^{2}})+{\bar {q}}(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ $(X(x,y),Y(x,y)):=(x^{q^{2}},y^{q^{2}})+{\bar {q}}( X y)$ $(l^{2}-3)/2$

Produsul punctual poate fi realizat cu metoda dublei și adunării , sau cu polinomul diviziunii a-lea. A doua abordare oferă: ${\bar {q}}(x,y)$ ${\bar {q)}$

{\bar {q}}(x,y)=(x_{\bar {q}},y_{\bar {q}})=\left(x-{\frac {\psi _{{ \bar {q}}-1}\psi _({\bar {q}}+1}}{\psi _{\bar {q}}^{2}}},{\frac {\psi _{ 2{\bar {q}}}}{2\psi _{\bar {q}}^{4}}}\right)

unde este polinomul diviziunii a n- a. Rețineți că este o funcție numai a lui x , să notăm această funcție cu . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\taxa)$

Trebuie să împărțim problema în două cazuri: cazul în care , și cazul în care . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

Cazul 1: $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$

Folosind formula de adunare pentru grupul , obținem: $E(\mathbb {F} _{q})$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ bară {q}}}}\right)^{2}-x^{q^{2}}-x_{\bar {q}}.

Rețineți că acest calcul este imposibil dacă ipoteza inegalității eșuează.

Acum putem restrânge alegerea coordonatei x pentru două posibilități, și anume cazurile pozitive și negative. Folosind coordonata y , determinăm care dintre cele două cazuri are loc. ${\bar {t)}$

Mai întâi arătăm că X este doar o funcție a lui x . Luați în considerare . Deoarece este par, prin înlocuirea cu , rescriem expresia ca $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/a)^{2}$ $q^{2}-1$ $y^{2}$ $x^{3}+Ax+B$

(x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}-\theta (x))

și avem

X(x)\equiv (x^{3}+Ax+B)((x^{3}+Ax+B)^{\frac {q^{2}-1}{2}}- \theta (x)){\bmod {\psi }}_{l}(x).

Acum, dacă pentru , atunci egalitatea este adevărată pentru $X\equiv x_{\bar {t}}^{q}{\bmod {\psi }}_{l}(x)$ ${\bar {t}}\in [0,(l-1)/2]$ ${\bar {t)}$

\phi ^{2}(P)\mp {\bar {t))\phi (P)+{\bar {q))P=O

pentru toate punctele de P l -torsiune.

După cum am menționat mai devreme, folosind Y și , putem determina acum care dintre cele două valori ( sau ) funcționează. Dă sens . Algoritmul lui Schoof reține valorile dintr-o variabilă pentru fiecare prim l considerat . $y_{\bar {t}}^{q}$ ${\bar {t)}$ ${\bar {t)}$ $-{\bar {t)}$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod {l}}$ $t_{l}$

Cazul 2: $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

Să presupunem că . Deoarece l este un număr prim impar, este imposibil pentru , și, prin urmare, . Din ecuația caracteristică rezultă că , și deci că . Rezultă că q este un pătrat modulo l . Lasă . Calculați și verificați dacă . Dacă da, atunci este , în funcție de coordonata y. $(x^{q^{2}},y^{q^{2}})={\bar {q}}(x,y)$ ${\bar {q}}(x,y)=-{\bar {q}}(x,y)$ ${\bar {t}}\neq 0$ ${\bar {t}}\phi (P)=2{\bar {q}}P$ ${\bar {t}}^{2}{\bar {q}}\equiv (2q)^{2}{\pmod {l}}$ $q\equiv w^{2}{\pmod {l)}$ $w\phi(x,y)$ $\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ ${\bar {q}}(x,y)=w\phi (x,y)$ $t_{l)$ $\pm 2w{\pmod {l}}$

Dacă q nu este pătrat modulo l , sau dacă egalitatea eșuează pentru unele w și , presupunerea noastră este greșită, deci . Ecuația caracteristică dă . $-w$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ $t_{l}=0$

Caz suplimentar $l=2$

Amintiți-vă, acordurile noastre inițiale nu iau în considerare cazul . Deoarece am presupus că q este impar și, în special, dacă și numai dacă are un element de ordin 2. După definiția adunării într-un grup, orice element de ordin 2 trebuie să aibă forma . Astfel, dacă și numai dacă polinomul are rădăcină în , dacă și numai dacă mcd . $l=2$ $q+1-t\equiv t{\pmod {2}}$ $t_{2}\equiv 0{\pmod {2)}$ $E(\mathbb {F} _{q})$ $(x_{0},0)$ $t_{2}\equiv 0{\pmod {2)}$ $x^{3}+Ax+B$ $\mathbb {F} _{q}$ $(x^{q}-x,x^{3}+Ax+B)\neq 1$

Algoritm

Intrare: 1. Curba eliptică .

E=y^{2}-x^{3}-Ax-B

2. Un întreg q pentru un câmp finit cu .

F_q

q=p^{b},b\geq 1

Concluzie: Numărul de puncte E peste .

F_q

Alegem un set de numere prime impare S , care nu conțin p , astfel încât Acceptăm dacă mcd , altfel acceptăm . Calculăm polinomul de diviziune .

N=\prod _{l\in S}l>4{\sqrt {q)).

t_{2}=0

(x^{q}-x,x^{3}+Ax+B)\neq 1

t_{2}=1

\psi _{l)

Toate calculele din bucla de mai jos sunt efectuate în inel Pentru că executăm : Fie singurul întreg astfel încât și . Calculăm , și . Dacă atunci Calculați . pentru a face : dacă atunci dacă atunci ; altfel . în caz contrar, dacă q este un pătrat modulo l , atunci calculați w cu calculate dacă atunci altfel dacă atunci altfel altfel Folosiți teorema chineză a restului pentru a calcula t modulo N din ecuația unde .

\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l}).

l\în S

{\bar {q)}

q\equiv {\bar {q}}{\pmod {l}}

\mid {\bar {q}}\mid <l/2

(x^{q},y^{q})

(x^{q^{2}},y^{q^{2}})

(x_{\bar {q)), y_{\bar {q)}}

x^{q^{2}}\neq x_{\bar {q}}

(X Y)

1\leq {\bar {t}}\leq (l-1)/2

X=x_{\bar {t}}^{q}

Y=y_{\bar {t}}^{q}

t_{l}={\bar {t)}

t_{l}=-{\bar {t))

q\equiv w^{2}{\pmod {l)}

w(x^{q},y^{q})

w(x^{q},y^{q})=(x^{q^{2}},y^{q^{2}})

t_{l}=2w

w(x^{q},y^{q})=(x^{q^{2}},-y^{q^{2}})

t_{l}=-2w

t_{l}=0

t_{l}=0

x\equiv t_{l}{\pmod {l)}

l\în S

Deducem .

q+1-t

Dificultate

Majoritatea calculelor implică calcularea și , pentru fiecare număr prim , adică calcularea , , , pentru fiecare număr prim . Calculele presupun exponențiere în inel și necesită înmulțiri. Deoarece gradul este , fiecare element din inel este un polinom de grad . Prin teorema numerelor prime, există aproximativ numere prime de mărime , care dă pentru , și obținem . Astfel, fiecare înmulțire din inel necesită înmulțiri în , care la rândul lor necesită operații pe biți. În total, numărul de operații pe biți pentru fiecare număr prim este . Presupunând că acest calcul trebuie făcut pentru fiecare dintre numerele prime, complexitatea totală a algoritmului lui Schuf devine . Utilizarea operațiilor polinomiale rapide și a aritmeticii întregi reduce acest timp la . $\phi (P)$ $\phi ^{2}(P)$ $l$ $x^{q}$ $y^{q)$ $x^{q^{2}}$ $y^{q^{2)}$ $l$ $R=\mathbb {F} _{q}[x,y]/(y^{2}-x^{3}-Ax-B,\psi _{l})$ $O(\log q)$ $\psi _{l)$ ${\frac {l^{2}-1}{2}}$ $O(l^{2})$ $O(\log q)$ $O(\log q)$ $l$ $O(\log q)$ $O(l^{2})=O(\log ^{2}q)$ $R$ $O(\log ^{4}q)$ $\mathbb {F} _{q}$ $O(\log ^{2}q)$ $l$ $O(\log ^{7}q)$ $O(\log q)$ $O(\log ^{8}q)$ ${\tilde {O}}(\log ^{5}q)$

Îmbunătățiri ale algoritmului Schuf

În anii 1990, Noam Elkis și apoi A. O. L. Atkin au venit cu îmbunătățiri ale algoritmului de bază Schuf prin restrângerea setului de numere prime la numere de un anumit tip. Aceste numere au devenit cunoscute ca numere prime Elkis și, respectiv, prime Atkin. Un număr prim se numește prim Elkis dacă egalitatea caracteristică este descompunabilă peste , iar numerele prime Atkin sunt prime care nu sunt prime Elkis. Atkin a arătat cum se combină informațiile obținute din primii Atkin cu informațiile obținute din numerele prime Elkis pentru a obține un algoritm eficient, care a fost numit „ Algoritmul Schoof-Elkis-Atkin . Prima sarcină este de a determina dacă un prim dat este un prim Elkis sau Atkin. Pentru a obține acest lucru, folosim polinoame modulare, care apar atunci când studiem formele modulare și interpretăm curbele eliptice peste câmpul numerelor complexe ca rețele. Odată ce determinăm ce caz avem, în loc să folosim polinoame de diviziune , putem lucra cu polinoame care au grade mai mici decât polinoamele de diviziune: în loc de . Pentru o implementare eficientă, sunt utilizați algoritmi probabilistici de găsire a rădăcinii, ceea ce face din algoritm un algoritm Las Vegas , mai degrabă decât un algoritm determinist. În baza ipotezei euristice că aproximativ jumătate dintre numerele prime mai mici sau egale cu sunt numere prime Elkis, se obține un algoritm care este mai eficient decât algoritmul lui Schoof, iar timpul de rulare așteptat al acestui algoritm este , dacă se utilizează aritmetică obișnuită și , dacă se utilizează aritmetică rapidă. Trebuie remarcat faptul că această ipoteză euristică este adevărată pentru majoritatea curbelor eliptice, dar nu este cunoscută pentru cazul general, chiar dacă ipoteza Riemann generalizată este adevărată . $S=\{l_{1},\ldots ,l_{s}\}$ $l$ $\phi ^{2}-t\phi +q=0$ $\mathbb {F} _{l)$ $O(l)$ $O(l^{2})$ $O(\log q)$ $O(\log ^{6}q)$ ${\tilde {O}}(\log ^{4}q)$

Implementări

Unii dintre algoritmi au fost implementați în C++ de Mike Scott și sunt disponibili în codul sursă . Implementarea este absolut gratuită (fără condiții, fără restricții), dar folosește biblioteca MIRACL , care este distribuită sub licența AGPLv3 .

Algoritmul lui Schuf cu implementare pentru cu simplu . $E(\mathbb {F} _{p})$ $p$
Algoritmul lui Schuf cu implementare pentru . $E(\mathbb {F} _{2^{m))}$

Vezi și

Criptografia eliptică
Numărarea punctelor pe o curbă eliptică
polinoame de împărțire
Endomorfismul Frobenius

Note

↑ Deși, articolul ECDSA spune următoarele: algoritmul lui Skoof este destul de ineficient în practică pentru valorile p care sunt cu adevărat de interes, adică p > 2 160 .
↑ Punctul mP, egal cu suma de m ori a punctului P din grupul aditiv al punctelor unei curbe eliptice, se numește produsul scalar al punctului și al numărului m , iar punctele mP în sine sunt numite multipli scalari ai punctul ( Rybolovlev 2004 ). În cartea lui Tiborg ( van Tilborg 2006 ) același concept este numit multiplu scalar.

Literatură

R. Schoof. Curbe eliptice peste câmpuri finite și calculul rădăcinilor pătrate mod p // Math. Comp.. - 1985. - T. 44 , nr. 170 . — S. 483–494 .
R. Schoof. Numărarea punctelor pe curbele eliptice peste câmpuri finite // J. Theor. Nombres Bordeaux. - 1995. - Emisiune. 7 . — S. 219–254 .
Gregg Musiker. Algoritmul lui Schoof pentru numărarea punctelor pe $E(\mathbb {F} _{q})$ . — 2005.
V. Müller. Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern . - Saarbrücken: Universität des Saarlandes, 1991. - (Teza de master).
Andreas Enge. Curbele eliptice și aplicațiile lor la criptografie: o introducere. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington. Curbe eliptice: teoria numerelor și criptografia. - New York: Chapman & Hall / CRC, 2003. - V. 50. - (Matematica discretă și aplicațiile sale). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. Un curs de teoria numerelor și criptografie. - A doua editie. - Springer-Verlag, 1994. - V. 114. - (Texte de absolvire a matematicii). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. Fundamentele criptologiei. - Moscova: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitri Rybolovlev. Utilizarea criptografiei cu curbe eliptice în securitatea WEB . — 2004.

Algoritmi teoretici numerelor
Teste de simplitate	Miller Miller - Rabin Luca - Lemaire pepina Agrawala - Kayala - Saxonia Privighetoarea - Strassen
Găsirea numerelor prime	Iterarea peste divizori Sita lui Eratosthenes sita lui Atkin Sieve Sundarama
Factorizarea	Iterarea peste divizori Metoda Fermat p −1 Metoda Pollard Algoritmul ρ al lui Pollard metoda Lehmann Metoda curbei eliptice (algoritmul lui Lenstra) algoritmul lui Dixon Sita pătrată
Logaritm discret	Algoritmul Gelfond-Shanks Algoritmul Polig-Hellman Metoda ρ a lui Pollard Algoritmul Cangurului lui Pollard Algoritmul lui Adleman Algoritmul COS
Găsirea GCD	algoritmul lui Euclid Algoritm avansat Algoritm binar
Modul de aritmetică	Algoritmul lui Montgomery Teorema chineză a restului
Înmulțirea și împărțirea numerelor	Algoritmul Karatsuba Algoritmul Toom-Cook Algoritmul Schönhage-Strassen Algoritmul Fuhrer Algoritmul Harvey-van der Hoeven Algoritmul Burnickel-Ziegler
Calcularea rădăcinii pătrate	Algoritmul Tonelli-Shanks Algoritmul Berlekamp-Rabin