Schoof–Elkies–Atkin-algoritm

Schoof –Elkies–Atkin-algoritmen (SEA) är en algoritm som används för att hitta ordningen på eller beräkna antalet punkter på en elliptisk kurva över ett ändligt fält . Dess primära tillämpning är i elliptisk kurvkryptografi . Algoritmen är en förlängning av Schoofs algoritm av Noam Elkies och AOL Atkin för att avsevärt förbättra dess effektivitet (under heuristiska antaganden).

Detaljer

Elkies-Atkin-tillägget till Schoofs algoritm fungerar genom att begränsa uppsättningen av primtal $S=\{l_{1},\ldots ,l_{s}\}$ anses vara primtal av ett visst slag. Dessa kom att kallas Elkies primtal respektive Atkin primtal. Ett primtal $l$ kallas Elkies-primtal om den karakteristiska ekvationen: $\phi ^{2}-t\phi +q=0$ delas över ${\ displaystyle \mathbb {F} _{l}}$ , medan ett Atkin-primtal är ett primtal som inte är ett Elkies-primtal. Atkin visade hur man kombinerar information erhållen från Atkin-primtalen med informationen som erhålls från Elkies-primtal för att producera en effektiv algoritm, som kom att kallas Schoof–Elkies–Atkin-algoritmen. Det första problemet att ta itu med är att avgöra om ett givet primtal är Elkies eller Atkin. För att göra det använder vi modulära polynom $\Phi _{l}(X,Y)$ som parametriserar par av $l$ - isogena elliptiska kurvor i termer av deras j-invarianter (i praktiken kan alternativa modulära polynom också användas men för samma ändamål).

Om det instansierade polynomet $\Phi _{l}(X,j(E))$ har en rot $j(E')$ i $\mathbb {F} _{q}$ så är $l$ ett Elkies primtal, och vi kan beräkna ett polynom $f_{l}(X)$ vars rötter motsvarar punkter i kärnan i $l$ -isogenin från $E$ till $E'$ . Polynomet $f_{l}$ är en divisor av motsvarande divisionspolynom som används i Schoofs algoritm, och det har betydligt lägre grad, $O(l)$ mot $O(l^{2})$ . För Elkies primtal tillåter detta att man kan beräkna antalet punkter på $E$ modulo $l$ mer effektivt än i Schoofs algoritm. I fallet med ett Atkin-primtal kan vi få information från faktoriseringsmönstret för $\Phi _{l}(X,j(E))$ i ${\displaystyle \mathbb {F} _{l}[X]} ,$ vilket begränsar möjligheterna för antalet punkter modulo $l$ , men algoritmens asymptotiska komplexitet beror helt på Elkies primtal. Förutsatt att det finns tillräckligt många små Elkies-primtal (i genomsnitt förväntar vi oss att hälften av primtalen $l$ är Elkies-primtal), resulterar detta i en minskning av speltiden. Den resulterande algoritmen är probabilistisk (av Las Vegas- typ), och dess förväntade körtid är, heuristiskt sett, ${\tilde {O}}(\log ^{4}q)$ , vilket gör det mer effektivt i praktiken än Schoofs algoritm. Här ${\tilde {O}}$ en variant av stor O-notation som undertrycker termer som är logaritmiska i ett uttrycks huvudterm.

Genomföranden

Schoof–Elkies–Atkin-algoritmen är implementerad i PARI/GP- datoralgebrasystemet i GP-funktionens ellap.

externa länkar