Schoof's algorithm: Difference between revisions

Revision as of 14:47, 17 March 2009

Revision as of 18:10, 17 March 2009

Line 1:

'''Schoof's Algorithm''' is an an efficient algorihtmalgorithm to count points on [[elliptic curves]] over [[finite fields]]. The algorithm has applications in [[elliptic curve cryptography]] where it is important to know the number of points to judge the difficulty of solving the [[discrete logarithm problem]] in the [[group]] of points on an elliptic curve.

The algorithm was published by René Schoof in 1985 and it was a theoretical break through, as it was the first deterministic polynomial time algorithm for [[counting points on elliptic curves]]. Before Schoof's algorithm, approaches to [[counting points on elliptic curves]] such as the naive and [[baby-step giant-step]] algorithms were, for the most part, tedious and had an exponential running time.

Line 52:

==Computation modulo primes==

The <math>l</math>th [[division polynomial]] is such that its roots are precisely the <math>x</math> coordinates of points of order <math>l</math>. Thus, to restrict the computatio of <math>(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> to the <math>l</math>-torsion points means computing these expressions as functions in the coordinate ring of <math>E</math> ''and'' modulo the <math>l</math>th division polynomial. I.e. we are working in <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l})</math>. This means in particular that the degree of <math>X</math> and <math>Y</math> defined via <math>(X(x,y),Y(x,y)):=(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> is boundedat bymost 1 in <math>y</math> and byat most <math>(l^2-3)/2</math>

in <math>x</math>.

Line 71:

<math>

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}}.

</math>

Note that this computation fails in case the assumption of inequality was wrong.

Line 108:

==The Algorithm==

:(1) Choose a set of odd primes <math>S</math>, <math>p \notin S</math> such that <math>N=\prod_{l\in S} l > 2\sqrt{q}.</math>

:(2) Forput <math>l=2</math>, <math>t_{l}t_2=0</math> if and only if <math>\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>, else <math>t_{l}t_2=1</math>.

:(3) Forfor <math>l \in S\setminus \{2\}</math> do :

::(a) letLet <math>\bar{q}</math> be the unique integer such that <math>q \equiv \bar{q} \pmod l</math> and <math>\mid \bar{q} \mid< l/2</math>. Compute <math>\psi_l</math>. All following computations in this loop are in the following ring: <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}).</math>

::(eb)If Compute <math>\gcd(numerator(x^{q}-x_{w}), \phi_y^{lq})=1</math>, <math>t_(x^{lq^{2}-2w}, y^{q^{2}})</math>. Otherwiseand <math>t_(x_{l\bar{q}},y_{\equiv 2wbar{q}})</math> .

::(c) for if <math>1x^{q^{2}}\leqneq x_{\bar{tq}} \leq (l-1)/2</math> do then

:::(bi) compute <math>(X(x,Y) </math> as above.

:::(ii)for <math>1\leq \bar{t} \leq (l-1)/2</math> do

::::(iii)if <math>X = x^{q} _ {\bar{t}}</math> then

:::::(iiiv)if <math>(y'Y -= y^{q} _ {\bar{t}})/y \equiv 0 \pmod {\psi_{l}}</math> then <math>t_{l}=\bar{t}</math>; otherwiseelse <math>t_{l}=-\bar{t}</math> .

::(d)else if <math>q</math> is a square modulo <math>l</math> then

:::(i)compute <math>w</math> with <math>q\equiv w^{2} \pmod l</math>

:::(ii)compute <math>w(x^{q}, y^{q})</math>

:::(iii)if <math>w(x^{q}, y^{q})=(x^{q^{2}}, y^{q^{2}})</math> then <math>t_l=2w</math>

:::(iv)else if <math>w(x^{q}, y^{q})=(x^{q^{2}}, -y^{q^{2}})</math> then <math>t_l=-2w</math>

:::(v)else <math>t_{l}=0</math>

::(e)else <math>t_{l}=0</math>

:(4)Use the Chinese Remainder Theorem to compute <math>\sharp E(\mathbb{F}_{q}) \pmod{N2N}</math>.

(1)Note Choosethat asince the set of primes <math>S</math>, was chosen so that <math>p 2N>4\notin Ssqrt{q}</math>, suchby thatHasse's theorem, we <math>N=\prod_{l\in S}fact lknow <math> 4\sqrtsharp E(\mathbb{F}_{q})</math> precisely.

(2) For <math>l=2</math>, <math>t_{l}=0</math> if and only if <math>\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>, else <math>t_{l}=1</math>

(3) For <math>l \in S\setminus \{2\}</math> do

:(a) let <math>\bar{q}</math> be the unique integer such that <math>q \equiv \bar{q} \pmod l</math> and <math>\mid \bar{q} \mid< l/2</math>

:(b) compute <math>X(x)</math> as above.

::(i) if case 2, goto (d) to determine <math>t_l</math>; else

:(c) for <math>1\leq \bar{t} \leq (l-1)/2</math> do

::(i) if <math>X \equiv x^{q} _ {\bar{t}} \pmod {\psi_{l}}</math> go to ii. . Otherwise try next value of <math>\bar{t}</math>.

::(ii)if <math>(y' - y^{q} _ {\bar{t}})/y \equiv 0 \pmod {\psi_{l}}</math> then <math>t_{l}=\bar{t}</math>; otherwise <math>t_{l}=-\bar{t}</math>

:(d)Find <math>q</math>'s square roots modulo <math>l</math>,if they exist. If they don't exist then <math>t_{l}=0</math>. Otherwise let <math>q\equiv w^{2} \pmod l</math>

:(e)If <math>\gcd(numerator(x^{q}-x_{w}), \phi_{l})=1</math> <math>t_{l}-2w</math>. Otherwise <math>t_{l}\equiv 2w</math>

(4)Use Chinese Remainder Theorem to compute <math>\sharp E(\mathbb{F}_{q}) \pmod{N}</math>.

Note that since the set <math>S</math> was chosen so that <math>N>4\sqrt{q}</math>, by Hasse's theorem, we in fact know <math> \sharp E(\mathbb{F}_{q})</math> precisely.

==Complexity of Schoof's Algorithm==

Most of the computation is taken by the evaluation of <math>\phi(P)</math> and <math>\phi^{2}(P)</math>, for each prime <math>l</math>, that is computing <math>x^q</math>, <math>y^q</math>, <math>x^{q^2}</math>, <math>y^{q^2}</math> for each prime <math>l</math>. This involves exponentiation in the ring <math>R = \mathbb{F}_{q}[x, y]/ (y^2-x^3-Ax-B, \psi_l)</math> and requires <math>O(\log q)</math> multiplications. Since the degree of <math>\psi_l</math> is <math>\frac{l^2-1}{2}</math>, each element in the ring is a polynomial of degree <math>O(l^2)</math>. By the [[prime number theorem]], we have around <math>O(\log q)</math> primes of size <math>O(\log q)</math> giving that <math>l</math> is <math>O(\log q)</math> and we obtain that <math>O(l^2) = O(\log^2q)</math>. Thus each multiplication in the ring <math>R</math> requires <math>O(\log^4 q)</math> multiplications in <math>\mathbb{F}_{q}</math> which in turn requires <math>O(\log^2 q)</math> bit operations. In total, the number of bit operations for each prime <math>l</math> is <math>O(\log^7 q)</math>. ByGiven thethat [[primethis numbercomputation theorem]],needs weto havebe aroundcarried out for each of the <math>O(\log q)</math> primes, and thus the total complexity of Schoof's algorithm turns out to be <math>O(\log^78 q)</math>. \cdotNote O(\logthat q)fast =polynomial arithmetic reduces the costs down to <math>O(\log^85 q)</math>.

==Improvements to Schoof's Algorithm==

In the 1990s, [[Noam Elkies]], followed by [[A. O. L. Atkin]], devised improvements to Schoof's basic algorithm by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime <math>l</math> is called an Elkies prime if the characteristic equation: <math>\phi^2-t\phi+ q = 0</math> splits over <math>\mathbb{F}_l</math>, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the [[Schoof-Elkies-Atkin algorithm]]. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials, which come from the study of [[modular forms]] and an interpretation of [[Elliptic curve#Elliptic curves over the complex numbers|elliptic curves over the complex numbers]] as lattices. Once we have determined which case we are in, instead of using Division[[division Polynomialspolynomials]], we proceed by working modulo the modular polynomials <math>f_l</math> which have a lower degree than the corresponding division polynomial <math>\psi_l</math> (degree <math>O(l)</math> rather than <math>O(l^2)</math>). This results in a further reduction in the running time, giving us an algorithm more efficient than Schoof's, with complexity <math>O(\log^6 q)</math> for standard arithmetic and <math>O(\log^4 q)</math>.

==Implementations==