Schoof's algorithm: Difference between revisions

Revision as of 01:59, 15 March 2013

Revision as of 13:09, 8 September 2013

Line 22:

</math>

This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down <math>\sharp E(\mathbb{F}_{q})</math> to a finite (albeit large) set of possibilities. Defining <math>t</math> to be <math>q + 1 - \sharp E(\mathbb{F}_{q})</math>, and making use of this result, we now have that computing the cardinality of <math>t</math> modulo <math>N</math> where <math>N > 4\sqrt{q}</math>, is sufficient for determining <math>t</math>, and thus <math>\sharp E(\mathbb{F}_{q})</math>. While there is no efficient way to compute <math>t \pmod N</math> directly for general <math>N</math>, it is possible to compute <math>t \pmod l</math> for <math>l</math> a small prime, rather efficiently. We choose <math>S=\{l_1,l_2,...,l_r\}</math> to be a set of distinct primes such that <math>\prod l_i = N > 4\sqrt{q}</math>. Given <math>t \pmod l_i</math> for all <math>l_i\in S</math>, the [[Chinese remainder theorem]] allows us to compute <math>t \pmod N</math>.

In order to compute <math>t \pmod l</math> for a prime <math>l \neq p</math>, we make use of the theory of the Frobenius endomorphism <math>\phi</math> and [[division polynomials]]. Note that considering primes <math>l \neq p</math> is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case <math>q=p</math> since there are more efficient, so called <math>p</math> adic algorithms for small characteristic fields.

Line 41:

One could try to symbolically compute these points <math>(x^{q^{2}}, y^{q^{2}})</math>, <math>(x^{q}, y^{q})</math> and <math>q(x, y)</math> as functions in the [[Imaginary_hyperelliptic_curve#Coordinate_ring|coordinate ring]] <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B)</math> of <math>E</math>

and the search for a value of <math>t</math> which satisfies the equation. However, the degrees get very large and this approach is impractical.

Schoof's idea was to carry out this computation restricted to points of order <math>l</math> for various small primes <math>l</math>

Fixing an odd prime <math>l</math>, we now move on to solving the problem of determining <math>t_{l}</math>, defined as <math>t \pmod l</math>, for a given prime <math>l \neq 2, p</math>.

If a point <math>(x, y)</math> is in the <math>l</math>-[[torsion subgroup]] <math>E[l]=\{P\in E(\bar{\mathbb{F}_{q}}) \mid lP=O \}</math>, then <math>qP = \bar{q}P</math> where <math>\bar{q}</math> is the unique integer such that <math>q \equiv \bar{q} \pmod l</math> and <math>\mid \bar{q} \mid< l/2</math>.

Note that <math>\phi(O) = O</math> and that for any integer <math>r</math> we have <math>r\phi (P) = \phi (rP)</math>. Thus <math>\phi (P)</math> will have the same order as <math>P</math>. Thus for <math>(x, y)</math> belonging to <math>E[l]</math>, we also have <math>t(x^{q}, y^{q})= \bar{t}(x^{q}, y^{q})</math> if <math>t \equiv \bar{t} \pmod l</math>. Hence we have reduced our problem to solving the equation

: <math> (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) \equiv \bar{t}(x^{q}, y^{q}),</math>

Line 65:

<math>y_{\bar{q}}/y</math> is a function in <math>x</math> only and denote it by <math>\theta(x)</math>.

We must split the problem into two cases: the case in which <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>, and the case in which <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>. Note that these equalities are checked modulo <math>\psi_l</math>.

===Case 1: <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>===

By using the [[Elliptic_curves#The_group_law|addition formula]] for the group <math>E(\mathbb{F}_{q})</math> we obtain:

Line 75:

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

We are now able to use the <math>x</math>-coordinate to narrow down the choice of <math>\bar{t}</math> to two possibilities, namely the positive and negative case. Using the <math>y</math>-coordinate one later determines which of the two cases holds.

We first show that <math>X</math> is a function in <math>x</math> alone. Consider <math>(y^{q^{2}} - y_{\bar{q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar{q}}/y)^{2}</math>.

Since <math>q^{2}-1</math> is even, by replacing <math>y^{2}</math> by <math>x^3+Ax+B</math>, we rewrite the expression as

: <math>

Line 90:

</math>

Now if <math>X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x)</math> for one <math>\bar{t}\in [0,(l-1)/2]</math> then <math>\bar{t}</math> satisfies

: <math>

Line 96:

</math>

for all <math>l</math>-torsion points <math>P</math>.

As mentioned earlier, using <math>Y</math> and <math>y_{\bar{t}}^{q}</math> we are now able to determine which of the two values of <math>\bar{t}</math> (<math>\bar{t}</math> or <math>-\bar{t}</math>) works. This gives the value of <math>t\equiv \bar{t}\pmod l</math>. Schoof's algorithm stores the values of <math>\bar{t}\pmod l</math> in a variable <math>t_l</math> for each prime <math>l</math> considered.