Shufs algoritme

Schufs algoritme er en effektiv algoritme [1] til at tælle antallet af punkter på en elliptisk kurve over et begrænset felt . Algoritmen har applikationer i elliptisk kryptografi , hvor det er vigtigt at kende antallet af punkter for at bedømme vanskeligheden ved at løse et diskret logaritmeproblem på en gruppe af punkter på en elliptisk kurve.

Algoritmen blev udgivet i 1985 af René Chouf og det var et teoretisk gennembrud, da det var den første deterministiske polynomielle tidsalgoritme til at tælle punkter på en elliptisk kurve . Før Schufs algoritme var tilgange til at tælle punkter på elliptiske kurver, såsom den simple algoritme for små og store trin , for det meste besværlige og krævede eksponentiel køretid.

Denne artikel forklarer Schufs tilgang med fokus på de matematiske ideer bag algoritmen.

Introduktion

Lade være en elliptisk kurve defineret over et endeligt felt , hvor for primtal og heltal . Over et felt med karakteristik kan en elliptisk kurve gives (kort) af Weierstrass-ligningen $E$ $\mathbb {F} _{q}$ $q=p^{n}$ $s$ $n\geq 1$ $\neq 2,3$

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

med . Sættet af punkter defineret over består af løsninger, der opfylder ligningen for kurven og punktet ved uendelig . Hvis man bruger gruppeloven om elliptiske kurver på denne mængde, kan man se, at denne mængde danner en abelsk gruppe , hvor den fungerer som nul-elementet. For at tælle punkter på en elliptisk kurve beregner vi sættets kardinalitet . Schuf-tilgangen bruger Hasses elliptiske kurvesætning , sammen med den kinesiske restsætning og divisionspolynomier til at beregne kardinaliteten . ${\displaystyle A,B\in \mathbb {F} _{q))$ $\mathbb {F} _{q}$ ${\displaystyle (a,b)\in \mathbb {F} _{q}^{2))$ $O$ $E(\mathbb {F} _{q})$ $O$ $E(\mathbb {F} _{q})$ $\sharp E(\mathbb {F} _{q})$

Hasses sætning

Hasses sætning siger, at hvis er en elliptisk kurve over et endeligt felt, så opfylder uligheden ${\displaystyle 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)).

Dette stærke resultat, opnået af Hasse i 1934, forenkler vores opgave ved at indsnævre det til et begrænset (skønt stort) sæt af muligheder. Hvis vi bestemmer hvordan og bruger dette resultat, får vi, at beregningen af effektmodulo , hvor , er tilstrækkelig til at beregne , og derfor til at opnå . Selvom der ikke er nogen effektiv måde at beregne direkte for generelle tal, er det muligt at beregne et lille primtal ret effektivt. Vi vælger som et sæt af forskellige primtal, sådan at . Hvis givet for alle , giver den kinesiske restsætning dig mulighed for at beregne . $\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}}$ ${\displaystyle t{\pmod {l_{i))))$ $l_{i}\in S$ $t{\pmod {N}}$

For at beregne for primtal bruger vi Frobenius endomorfismeteori og divisionspolynomier . Bemærk, at det ikke giver problemer at overveje primtal , da vi altid kan vælge et større primtal for at sikre, at produktet er stort nok. Under alle omstændigheder bruges Schuf-algoritmen oftest til casen , da der er mere effektive, såkaldte -adiske algoritmer, til felter med lille karakteristik. $t{\pmod {l}}$ $l\neq p$ $\phi$ $l\neq p$ $q=p$ $s$

Frobenius endomorfisme

Givet en elliptisk kurve defineret over , overvejer vi punkter på over , den algebraiske lukning af feltet . Det vil sige, at vi tillader punkter at have koordinater i . Frobenius-endomorfismen strækker sig over en elliptisk kurve med en kortlægning . $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})$

Dette kort er identisk med og kan udvides med et punkt til det uendelige , hvilket gør det til en gruppemorfisme fra sig selv. $E(\mathbb {F} _{q})$ $O$ $E({\bar {\mathbb {F} _{q))})$

Frobenius endomorfismen opfylder en andengradsligning relateret til magt ved følgende sætning: $E(\mathbb {F} _{q})$

Sætning: Frobenius-endomorfien givet ved kortlægningen opfylder den karakteristiske ligning $\phi$

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

, hvor

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

Så for alt , hvad vi har , hvor + betyder tilføjelsen af en elliptisk kurve, og og betyder skalarproduktet af et punkt på og et punkt på [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$

Du kan prøve at beregne disse punkter i symbolsk form , og som funktioner på koordinatringen på kurven , og så lede efter en værdi , der opfylder ligningen. Graderne viser sig dog at være meget store, og denne tilgang har ingen praktisk værdi. $(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$

Schufs idé var at udføre sådanne beregninger og begrænse sig til at bestille point for forskellige små primtal . Ved at rette et ulige primtal fortsætter vi med at løse problemet med at bestemme , defineret som , for et givet primtal . Hvis punktet er i -torsion undergruppen af , Så , Hvor er det eneste heltal sådan at og . Bemærk det og det for ethvert heltal , vi har . Har således samme rækkefølge som . Så for , som hører til , har vi også hvis . Derfor har vi reduceret vores problem til at løse ligningen $l$ $l$ $l$ ${\displaystyle t_{l))$ $t{\pmod {l}}$ $l\neq 2,p$ $(x, y)$ $l$ ${\displaystyle E[l]=\{P\in E({\bar {\mathbb {F} _{q))})\midt 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}),

hvor og ligge i intervallet . ${\bar {t))$ ${\bar {q))$ $[-(l-1)/2,(l-1)/2]$

Beregninger modulo

Divisionspolynomiet med indeks l er et polynomium, således at dets rødder er nøjagtigt x - koordinaterne af ordenspunkter l . Så betyder begrænsningen af beregningentil l -torsionspunkterne beregningen af disse udtryk som funktioner af koordinatringen E og modulet af det l -te divisionspolynomium. Det vil sige, at vi arbejder i. Dette betyder især, at graden af X og Y defineret afikke overstiger 1 med hensyn til variablen y ogmed hensyn til variablen 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$

Punktproduktet kan udføres med dobbelt-og-tilføj- metoden eller med th divisionspolynomiet. Den anden tilgang giver: ${\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)

hvor er det n . divisionspolynomium. Bemærk, at det kun er en funktion af x , lad os betegne denne funktion med . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\theta (x)$

Vi skal opdele problemet i to tilfælde: det tilfælde, hvor , og det tilfælde, hvor . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

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

Ved at bruge additionsformlen for gruppen får vi: $E(\mathbb {F} _{q})$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ søjle {q}}}}\højre)^{2}-x^{q^{2}}-x_{\bar {q}}.

Bemærk, at denne beregning er umulig, hvis ulighedsantagelsen mislykkes.

Vi kan nu indsnævre valget af x -koordinaten for to muligheder, nemlig de positive og negative tilfælde. Ved hjælp af y- koordinaten bestemmer vi, hvilket af de to tilfælde, der finder sted. ${\bar {t))$

Vi viser først, at X kun er en funktion af x . Overvej . Da det er lige, omskriver vi udtrykket ved at erstatte det med $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/å)^{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))

og det har vi

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

Nu, hvis for , så gælder ligheden for $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

for alle punkter af P l -torsion.

Som tidligere nævnt, ved hjælp af Y og , kan vi nu bestemme, hvilken af de to værdier ( eller ) der virker. Det giver mening . Schoofs algoritme husker værdierne i en variabel for hver betragtet primtal l . $y_{\bar {t}}^{q}$ ${\bar {t))$ ${\bar {t))$ $-{\bar {t))$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod {l}}$ $t_{l}$

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

Lad os antage det . Da l er et ulige primtal, er det umuligt for , og derfor . Det følger af den karakteristiske ligning, at , og derfor at . Det følger heraf, at q er en kvadratisk modulo l . Lad . Beregn ind og tjek om . Hvis ja, så er , afhængigt af y-koordinaten. $(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)$ ${\displaystyle t_{l))$ $\pm 2w{\pmod {l))$

Hvis q ikke er kvadratisk modulo l , eller hvis ligheden fejler for nogle w og , er vores antagelse forkert, så . Den karakteristiske ligning giver . $-w$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ $t_{l}=0$

Yderligere sag $l=2$

Husk, at vores oprindelige aftaler ikke tager højde for sagen . Da vi antog, at q er ulige, og især hvis og kun hvis det har et element af orden 2. Ved definitionen af addition i en gruppe skal ethvert element af orden 2 have formen . Således, hvis og kun hvis polynomiet har en rod i , hvis og kun hvis gcd . $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$

Algoritme

Input: 1. Elliptisk kurve .

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

2. Et heltal q for et endeligt felt med .

F_q

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

Konklusion:Antal E -point over .

F_q

Vi vælger et sæt ulige primtal S , der ikke indeholder p , sådan at vi accepterer hvis gcd , ellers accepterer vi . Vi beregner divisionspolynomiet .

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

t_{2}=0

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

t_{2}=1

{\displaystyle \psi _{l))

Alle beregninger i løkken nedenfor udføres i ringen For vi udfører : Lad være det eneste heltal sådan at og . Vi beregner , og . Hvis så Beregn . for at gøre : hvis så hvis da ; ellers . ellers hvis q er en kvadratisk modulo l så beregn w med beregn hvis så ellers hvis så ellers ellers Brug den kinesiske restsætning til at beregne t modulo N ud fra ligningen hvor .

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

l\in 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\in S

Vi udleder .

q+1-t

Sværhedsgrad

De fleste beregninger involverer beregning og , for hvert primtal , det vil sige beregning , , , for hvert primtal . Beregningerne involverer eksponentiering i ringen og kræver multiplikationer. Da graden er , er hvert element i ringen et polynomium af grad . Ved primtalssætningen er der omkring primtal af størrelse , som giver for , og vi får . Hver multiplikation i ringen kræver således multiplikationer i , hvilket igen kræver bitvise operationer. I alt er antallet af bitoperationer for hvert primtal . Hvis man antager, at denne beregning skal udføres for hver af primtallene, bliver den samlede kompleksitet af Schufs algoritme . Brug af hurtige polynomieoperationer og heltalsaritmetik reducerer denne tid til . $\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)$ ${\displaystyle \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)$

Forbedringer af Schuf-algoritmen

I 1990'erne kom Noam Elkis og derefter A. O. L. Atkin med forbedringer til den grundlæggende Schuf-algoritme ved at begrænse sættet af primtal til tal af en bestemt art. Disse tal blev kendt som henholdsvis Elkis-primtal og Atkin-primtal. Et primtal kaldes et Elkis-primtal, hvis den karakteristiske lighed er nedbrydelig over , og Atkin-primtal er primtal, der ikke er Elkis-primtal. Atkin viste, hvordan man kombinerer information opnået fra Atkin-primtal med information opnået fra Elkis-primtal for at opnå en effektiv algoritme, som blev kaldt " Schof-Elkis-Atkin-algoritmen . Den første opgave er at bestemme, om en given primtal er en Elkis- eller Atkin-primtal. For at få dette bruger vi modulære polynomier, som opstår, når man studerer modulære former og fortolker elliptiske kurver over komplekse tals felt som gitter. Når vi først har afgjort, hvilket tilfælde vi har, kan vi i stedet for at bruge divisionspolynomier arbejde med polynomier, der har lavere grader end divisionspolynomier: i stedet for . For effektiv implementering anvendes probabilistiske rodfindende algoritmer, som gør algoritmen til en Las Vegas-algoritme snarere end en deterministisk algoritme. Under den heuristiske antagelse, at omkring halvdelen af primtal mindre end eller lig med er Elkis-primtal, giver dette en algoritme, der er mere effektiv end Schoofs algoritme, og den forventede køretid for denne algoritme er , hvis du bruger almindelig aritmetik, og , hvis du bruger hurtig aritmetik. Det skal bemærkes, at denne heuristiske antagelse er sand for de fleste elliptiske kurver, men er ikke kendt for det generelle tilfælde, selvom den generaliserede Riemann-hypotese er sand . $S=\{l_{1},\ldots ,l_{s}\}$ $l$ $\phi ^{2}-t\phi +q=0$ ${\displaystyle \mathbb {F} _{l))$ $O(l)$ $O(l^{2})$ $O(\log q)$ $O(\log ^{6}q)$ ${\tilde {O}}(\log ^{4}q)$

Implementeringer

Nogle af algoritmerne er blevet implementeret i C++ af Mike Scott og er tilgængelige i kildekoden . Implementeringen er helt gratis (ingen betingelser, ingen begrænsninger), men bruger MIRACL- biblioteket , som distribueres under AGPLv3- licensen .

Schufs algoritme med implementering til med simple . $E(\mathbb {F} _{p})$ $s$
Schufs algoritme med implementering til . $E(\mathbb {F} _{2^{m)))$

Se også

Elliptisk kryptografi
Tælle punkter på en elliptisk kurve
divisionspolynomier
Frobenius endomorfisme

Noter

↑ Selvom ECDSA- artiklen siger følgende: Skoofs algoritme er ret ineffektiv i praksis for p -værdier , der virkelig er af interesse, dvs. p > 2 160 .
↑ Punktet mP, der er lig med m-fold addition af punktet P i den additive gruppe af punkter i en elliptisk kurve, kaldes skalarproduktet af punktet og tallet m , og selve punkterne mP kaldes skalære multipla af punktet ( Rybolovlev 2004 ). I Tiborgs bog ( van Tilborg 2006 ) kaldes det samme begreb for et skalært multiplum.

Litteratur

R. Schoof. Elliptiske kurver over endelige felter og beregningen af kvadratrødder mod p // Math. Komp.. - 1985. - T. 44 , no. 170 . — S. 483–494 .
R. Schoof. Tælle punkter på elliptiske kurver over endelige felter // J. Theor. Nombres Bordeaux. - 1995. - Udgave. 7 . — S. 219–254 .
Gregg Musiker. Schoofs algoritme til at tælle point på $E(\mathbb {F} _{q})$ . - 2005.
V. Müller. Die Berechnung der Punktanzahl von elliptiske kurven über endlichen Primkörpern . - Saarbrücken: Universität des Saarlandes, 1991. - (Kandidatafhandling).
Andreas Enge. Elliptiske kurver og deres anvendelser til kryptografi: en introduktion. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington. Elliptiske kurver: Talteori og kryptografi. - New York: Chapman & Hall / CRC, 2003. - V. 50. - (Diskret matematik og dens anvendelser). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. Et kursus i talteori og kryptografi. - Anden version. - Springer-Verlag, 1994. - V. 114. - (Kandidattekster i matematik). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. Grundlæggende om kryptologi. - Moskva: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitry Rybolovlev. Brug af elliptisk kurvekryptering i WEB-sikkerhed . – 2004.

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