Shufs algoritm

Schufs algoritm är en effektiv algoritm [1] för att räkna antalet punkter på en elliptisk kurva över ett ändligt fält . Algoritmen har applikationer inom elliptisk kryptografi , där det är viktigt att veta antalet punkter för att bedöma svårigheten att lösa ett diskret logaritmproblem på en grupp av punkter på en elliptisk kurva.

Algoritmen publicerades 1985 av René Chouf och det var ett teoretiskt genombrott eftersom det var den första deterministiska polynomtidsalgoritmen för att räkna punkter på en elliptisk kurva . Före Schufs algoritm var tillvägagångssätt för att räkna punkter på elliptiska kurvor, såsom den enkla algoritmen för små och stora steg , för det mesta arbetskrävande och krävde exponentiell körtid.

Den här artikeln förklarar Schufs tillvägagångssätt, med fokus på de matematiska idéerna bakom algoritmen.

Inledning

Låta vara en elliptisk kurva definierad över ett ändligt fält , där för primtal och heltal . Över ett fält med karakteristik kan en elliptisk kurva ges (kortfattat) av Weierstrass ekvation $E$ $\mathbb {F} _{q}$ $q=p^{n}$ $sid$ $n\geq 1$ $\neq 2,3$

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

med . Uppsättningen av punkter som definieras över består av lösningar som uppfyller ekvationen för kurvan och punkten i oändligheten . Om man använder grupplagen om elliptiska kurvor på denna mängd kan man se att denna mängd bildar en abelisk grupp , där den fungerar som nollelementet. För att räkna poäng på en elliptisk kurva, beräknar vi uppsättningens kardinalitet . Schuf-metoden använder Hasses elliptiska kurvsats , tillsammans med den kinesiska restsatsen och divisionspolynomen för att beräkna 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 teorem

Hasses teorem säger att om är en elliptisk kurva över ett ändligt fält så uppfyller olikheten ${\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)).

Detta starka resultat, som Hasse erhöll 1934, förenklar vår uppgift genom att begränsa den till en ändlig (men stor) uppsättning möjligheter. Om vi bestämmer hur och använder detta resultat får vi att beräkningen av effektmodulen , där , är tillräcklig för att beräkna , och därför för att få . Även om det inte finns något effektivt sätt att beräkna direkt för allmänna tal, är det möjligt att beräkna ett litet primtal ganska effektivt. Vi väljer som en uppsättning av olika primtal, så att . Om det ges för alla låter den kinesiska restsatsen dig beräkna . $\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}}$

För att beräkna för primtal använder vi Frobenius endomorfismteorin och divisionspolynom . Observera att det inte leder till problem att ta hänsyn till primtal , eftersom vi alltid kan välja ett större primtal för att säkerställa att produkten är tillräckligt stor. I vilket fall som helst används Schuf-algoritmen oftast för fallet eftersom det finns mer effektiva, så kallade -adiska algoritmer, för fält med liten karakteristik. $t{\pmod {l}}$ $l\neq p$ $\phi$ $l\neq p$ $q=p$ $sid$

Frobenius endomorphism

Med tanke på en elliptisk kurva definierad över , anser vi punkter på över , den algebraiska stängningen av fältet . Det vill säga vi tillåter punkter att ha koordinater i . Frobenius endomorphism över sträcker sig en elliptisk kurva med en kartläggning . $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})$

Denna karta är identisk med och kan förlängas med en punkt till oändligheten , vilket gör den till en gruppmorfism från sig själv. $E(\mathbb {F} _{q})$ $O$ $E({\bar {\mathbb {F} _{q))})$

Frobenius-endomorfismen uppfyller en andragradsekvation relaterad till makt genom följande teorem: $E(\mathbb {F} _{q})$

Teorem: Frobenius-endomorfismen som ges av kartläggningen uppfyller den karakteristiska ekvationen $\phi$

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

, var

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

Sedan för allt vi har , där + betyder tillägget av en elliptisk kurva, och och betyder skalärprodukten av en punkt på och en 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 försöka beräkna dessa punkter i symbolisk form , och som funktioner på koordinatringen på kurvan , och sedan leta efter ett värde som uppfyller ekvationen. Examina visar sig dock vara mycket stora och detta tillvägagångssätt har inget praktiskt värde. $(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 att utföra sådana beräkningar och begränsa sig till att beställa poäng för olika små primtal . Genom att fixa ett udda primtal fortsätter vi att lösa problemet med att bestämma , definierat som , för ett givet primtal . Om punkten är i -torsion undergruppen av , då , där är det enda heltal så att och . Notera det och det för alla heltal vi har . Har alltså samma ordning som . Sedan för , som hör till , har vi också om . Följaktligen har vi reducerat vårt problem till att lösa ekvationen $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))})\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}),

var och ligga i intervallet . ${\bar {t))$ ${\bar {q))$ $[-(l-1)/2,(l-1)/2]$

Beräkningar modulo

Divisionspolynomet med index l är ett polynom så att dess rötter är exakt x -koordinaterna för ordningspunkter l . Då innebär begränsningen av beräkningentill l -torsionspunkterna beräkningen av dessa uttryck som funktioner av koordinatringen E och modulen för det l -:e divisionspolynomet. Det vill säga vi arbetar i. Detta innebär i synnerhet att graden av X och Y definierade avinte överstiger 1 med avseende på variabeln y ochmed avseende på variabeln 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$

Prickprodukten kan göras med dubbel-och-lägg- metoden eller med th divisionspolynomet. Det andra tillvägagångssättet ger: ${\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)

var är n :te divisionspolynomet. Observera att det endast är en funktion av x , låt oss beteckna denna funktion med . $\psi_{{n}}$ $y_{\bar {q}}/y$ $\theta (x)$

Vi måste dela upp problemet i två fall: fallet där , och fallet där . $(x^{q^{2}},y^{q^{2}})\neq \pm {\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=\pm {\bar {q}}(x,y)$

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

Med hjälp av additionsformeln för gruppen får vi: $E(\mathbb {F} _{q})$

X(x,y)=\left({\frac {y^{q^{2}}-y_{\bar {q}}}{x^{q^{2}}-x_{\ stapel {q}}}}\höger)^{2}-x^{q^{2}}-x_{\bar {q}}.

Observera att denna beräkning är omöjlig om ojämlikhetsantagandet misslyckas.

Vi kan nu begränsa valet av x -koordinaten för två möjligheter, nämligen de positiva och negativa fallen. Med hjälp av y -koordinaten bestämmer vi vilket av de två fallen som äger rum. ${\bar {t))$

Vi visar först att X endast är en funktion av x . Överväg . Eftersom det är jämnt, genom att ersätta med , skriver vi om uttrycket som $(y^{q^{2}}-y_{\bar {q)))^{2}=y^{2}(y^{q^{2}-1}-y_{\bar {q}}/y)^{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))

och vi har

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

Nu, om för , då gäller jämställdheten för $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

för alla punkter av P l -torsion.

Som tidigare nämnts, med hjälp av Y och , kan vi nu avgöra vilket av de två värdena ( eller ) som fungerar. Det ger mening . Schoofs algoritm kommer ihåg värdena i en variabel för varje primtal l som betraktas . $y_{\bar {t}}^{q}$ ${\bar {t))$ ${\bar {t))$ $-{\bar {t))$ $t\equiv {\bar {t}}{\pmod {l}}$ ${\bar {t}}{\pmod {l}}$ $t_{l}$

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

Låt oss anta det . Eftersom l är ett udda primtal är det omöjligt för , och därför . Det följer av den karakteristiska ekvationen att , och därför att . Det följer att q är en kvadratisk modulo l . Låt . Beräkna in och kontrollera om . Om så är fallet är det , beroende på 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))$

Om q inte är kvadratisk modulo l , eller om likheten misslyckas för vissa w och , är vårt antagande fel, så . Den karakteristiska ekvationen ger . $-w$ $(x^{q^{2}},y^{q^{2}})=+{\bar {q}}(x,y)$ $(x^{q^{2}},y^{q^{2}})=-{\bar {q}}(x,y)$ $t_{l}=0$

Ytterligare fall $l=2$

Kom ihåg att våra initiala avtal inte tar hänsyn till fallet . Eftersom vi antog att q är udda, och i synnerhet om och endast om det har ett element av ordning 2. Enligt definitionen av addition i en grupp måste alla element av ordning 2 ha formen . Således, om och endast om polynomet har en rot i , om och endast om 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$

Algoritm

Inmatning: 1. Elliptisk kurva .

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

2. Ett heltal q för ett ändligt fält med .

F_q

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

Slutsats:Antal E poäng över .

F_q

Vi väljer en uppsättning udda primtal S , som inte innehåller p , så att vi accepterar om gcd , annars accepterar vi . Vi beräknar divisionspolynomet .

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))

Alla beräkningar i slingan nedan utförs i ringen För vi kör : Låta vara det enda heltal så att och . Vi beräknar och . Om sedan Beräkna . för att göra : om då om då ; annars . annars om q är en kvadratisk modulo l så beräkna w med beräkna om så annars om så annars Använd den kinesiska restsatsen för att beräkna t modulo N från ekvationen där .

\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 härleder .

q+1-t

Svårighet

De flesta beräkningar involverar beräkning och , för varje primtal , det vill säga beräkning , , , för varje primtal . Beräkningarna innebär exponentiering i ringen och kräver multiplikationer. Eftersom graden är , är varje element i ringen ett polynom av grad . Genom primtalssatsen finns det ungefär primtal av storlek , vilket ger för , och vi får . Varje multiplikation i ringen kräver alltså multiplikationer i , vilket i sin tur kräver bitvisa operationer. Totalt är antalet bitoperationer för varje primtal . Om man antar att denna beräkning behöver göras för vart och ett av primtalen, blir den totala komplexiteten för Schufs algoritm . Genom att använda snabba polynomoperationer och heltalsaritmetik minskar denna tid till . $\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)$

Förbättringar av Schuf-algoritmen

På 1990-talet kom Noam Elkis och sedan A. O. L. Atkin med förbättringar av den grundläggande Schuf-algoritmen genom att begränsa uppsättningen av primtal till tal av ett visst slag. Dessa tal blev kända som Elkis-primtal respektive Atkin-primtal. Ett primtal kallas ett Elkis-primtal om den karakteristiska likheten är nedbrytbar över , och Atkin-primtal är primtal som inte är Elkis-primtal. Atkin visade hur man kombinerar information erhållen från Atkin-primtal med information erhållen från Elkis-primtal för att få en effektiv algoritm, som kallades " Schof-Elkis-Atkin-algoritmen . Den första uppgiften är att avgöra om ett givet primtal är ett Elkis- eller Atkin-primtal. För att få detta använder vi modulära polynom, som uppstår när man studerar modulära former och tolkar elliptiska kurvor över komplexa tals fält som gitter. När vi väl har bestämt vilket fall vi har, istället för att använda divisionspolynom , kan vi arbeta med polynom som har lägre grader än divisionspolynom: istället för . För effektiv implementering används probabilistiska rotsökningsalgoritmer, vilket gör algoritmen till en Las Vegas-algoritm snarare än en deterministisk algoritm. Under det heuristiska antagandet att ungefär hälften av primtalen mindre än eller lika med är Elkis-primtal, ger detta en algoritm som är mer effektiv än Schoofs algoritm, och den förväntade körtiden för denna algoritm är , om man använder vanlig aritmetik, och , om man använder snabb aritmetik. Det bör noteras att detta heuristiska antagande är sant för de flesta elliptiska kurvor, men är inte känt för det allmänna fallet, även om den generaliserade Riemann-hypotesen är sann . $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)$

Implementeringar

Några av algoritmerna har implementerats i C++ av Mike Scott och är tillgängliga i källkod . Implementeringen är helt gratis (inga villkor, inga begränsningar), men använder MIRACL- biblioteket , som distribueras under AGPLv3- licensen .

Schufs algoritm med implementering för med enkel . $E(\mathbb {F} _{p})$ $sid$
Schufs algoritm med implementering för . $E(\mathbb {F} _{2^{m)))$

Se även

Elliptisk kryptografi
Räkna punkter på en elliptisk kurva
divisionspolynom
Frobenius endomorfism

Anteckningar

↑ Även om ECDSA -artikeln säger följande: Skoofs algoritm är ganska ineffektiv i praktiken för p -värden som verkligen är av intresse, dvs p > 2 160 .
↑ Punkten mP, lika med den m-faldiga additionen av punkten P i den additiva gruppen av punkter i en elliptisk kurva, kallas skalärprodukten av punkten och talet m , och själva punkterna mP kallas skalära multiplar av punkten ( Rybolovlev 2004 ). I Tiborgs bok ( van Tilborg 2006 ) kallas samma begrepp en skalär multipel.

Litteratur

R. Schoof. Elliptiska kurvor över ändliga fält och beräkningen av kvadratrötter mod p // Math. Comp.. - 1985. - T. 44 , nr. 170 . — S. 483–494 .
R. Schoof. Räkna punkter på elliptiska kurvor över ändliga fält // J. Theor. Nombres Bordeaux. - 1995. - Utgåva. 7 . — S. 219–254 .
Gregg Musiker. Schoofs algoritm för att räkna poäng på $E(\mathbb {F} _{q})$ . — 2005.
V. Müller. Die Berechnung der Punktanzahl von elliptiska kurven über endlichen Primkörpern . - Saarbrücken: Universität des Saarlandes, 1991. - (Masteruppsats).
Andreas Enge. Elliptiska kurvor och deras tillämpningar för kryptografi: en introduktion. - Dordrecht: Kluwer Academic Publishers, 1999.
Lawrence C. Washington. Elliptiska kurvor: talteori och kryptografi. - New York: Chapman & Hall / CRC, 2003. - V. 50. - (Diskret matematik och dess tillämpningar). — ISBN 978-1-4200-7146-7 .
Neal Koblitz. En kurs i talteori och kryptografi. - Andra upplagan. - Springer-Verlag, 1994. - V. 114. - (Examinerade texter i matematik). — ISBN 0-387-94293-9 .
H. C. A. van Tilborg. Grunderna i kryptologi. - Moskva: Mir, 2006. - ISBN 5-03-003639-3 UDC 519.6.
Dmitry Rybolovlev. Använda elliptisk kurvkryptering i webbsäkerhet . – 2004.

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