|
==Computation modulo primes==
The <math>{{mvar|l</math>}}th [[division polynomial]] is such that its roots are precisely the <math>{{mvar|x</math>}} coordinates of points of order <math>{{mvar|l</math>}}. Thus, to restrict the computation of <math>(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> to the <math>{{mvar|l</math>}}-torsion points means computing these expressions as functions in the coordinate ring of <math>{{mvar|E</math>}} ''and'' modulo the <math>{{mvar|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>{{mvar|X</math>}} and <math>{{mvar|Y</math>}} defined via <math>(X(x,y),Y(x,y)):=(x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y)</math> is at most 1 in <math>{{mvar|y</math>}} and at most <math>(l^2-3)/2</math>
in <math>{{mvar|x</math>}}.
The scalar multiplication <math>\bar{q}(x, y)</math> can be done either by [[exponentiation by squaring|double-and-add]] methods or by using the <math>\bar{q}</math>th division polynomial. The latter approach gives:
</math>
where <math>\psi_{n}</math> is the <math>{{mvar|n</math>}}th division polynomial. Note that
<math>y_{\bar{q}}/y</math> is a function in <math>{{mvar|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>.
{{fake heading|sub===3|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:
Note that this computation fails in case the assumption of inequality was wrong.
We are now able to use the <math>{{mvar|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>{{mvar|y</math>}}-coordinate one later determines which of the two cases holds.
We first show that <math>{{mvar|X</math>}} is a function in <math>{{mvar|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>
for all <math>{{mvar|l</math>}}-torsion points <math>{{mvar|P</math>}}.
As mentioned earlier, using <math>{{mvar|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>{{mvar|l</math>}} considered.
{{fake heading|sub===3|Case 2 : <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>===}}
We begin with the assumption that <math>(x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y)</math>. Since <math>{{mvar|l</math>}} is an odd prime it cannot be that <math>\bar{q}(x, y)=-\bar{q}(x, y)</math> and thus <math>\bar{t}\neq 0</math>. The characteristic equation yields that <math>\bar{t} \phi(P) = 2\bar{q} P</math>. And consequently that <math>\bar{t}^{2}\bar{q} \equiv (2q)^{2} \pmod l</math>.
This implies that <math>{{mvar|q</math>}} is a square modulo <math>{{mvar|l</math>}}. Let <math>q \equiv w^{2} \pmod l</math>. Compute <math>w\phi(x,y)</math> in <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l})</math> and check whether <math>
\bar{q}(x, y)=w\phi(x,y)</math>. If so, <math>t_{l}</math> is <math>\pm 2w \pmod l</math> depending on the y-coordinate.
If <math>{{mvar|q</math>}} turns out not to be a square modulo <math>{{mvar|l</math>}} or if the equation does not hold for any of <math>{{mvar|w</math>}} and <math>-w</math>, our assumption that <math>(x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y)</math> is false, thus <math>(x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y)</math>. The characteristic equation gives <math>t_l=0</math>.
{{fake heading|sub===3|Additional case <math>l = 2</math>===}}
If you recall, our initial considerations omit the case of <math>l = 2</math>.
Since we assume <math>{{mvar|q</math>}} to be odd, <math>q + 1 - t \equiv t \pmod 2</math> and in particular, <math>t_{2} \equiv 0 \pmod 2</math> if and only if <math>E(\mathbb{F}_{q})</math> has an element of order 2. By definition of addition in the group, any element of order 2 must be of the form <math>(x_{0}, 0)</math>. Thus <math>t_{2} \equiv 0 \pmod 2</math> if and only if the polynomial <math>x^{3} + Ax + B</math> has a root in <math>\mathbb{F}_{q}</math>, if and only if <math>\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>.
==The algorithm==
| 