Schoof's algorithm: Difference between revisions

Revision as of 03:45, 8 May 2018

Revision as of 12:20, 10 May 2018

Line 67:

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:

Line 102:

As mentioned earlier, using {{mvar|Y}} 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 {{mvar|l}} 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 {{mvar|l}} 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 {{mvar|q}} is a square modulo {{mvar|l}}. 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>

Line 109:

If {{mvar|q}} turns out not to be a square modulo {{mvar|l}} or if the equation does not hold for any of {{mvar|w}} 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 {{mvar|q}} 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>.