Schoof's algorithm: Difference between revisions

Revision as of 19:23, 5 September 2012

Revision as of 19:29, 5 September 2012

Line 112:

==The algorithm==

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

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

::(a3) Let <math>\bar{q}</math> beCompute the unique integer such thatdivision <math>q \equiv \bar{q} \pmod l</math> and <math>\mid \bar{q} \mid< l/2</math>. Computepolynomial <math>\psi_l</math>. All following computations in thisthe loop below are performed in the following ring: <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l}).</math>

:(34) for For <math>l \in S</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>. 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>

::(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^{q}, y^{q})</math>, <math>(x^{q^{2}}, y^{q^{2}})</math> and <math>(x_{\bar{q}},y_{\bar{q}})</math> .

::(c) if <math>x^{q^{2}}\neq x_{\bar{q}}</math> then

:::(i) computeCompute <math>(X,Y) </math>.

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

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

:::::(iv) if <math>Y = y^{q} _ {\bar{t}}</math> then <math>t_{l}=\bar{t}</math>; else <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>

:(45) Use the [[Chinese Remainder Theorem]] to compute <math>t</math> modulo <math>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>t</math> and <math> \sharp E(\mathbb{F}_{q}) = q+1-t</math> precisely.