Schoof's algorithm: Difference between revisions

Revision as of 14:13, 17 March 2009

Revision as of 14:47, 17 March 2009

Line 44:

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

Line 96:

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

We begin with the assumption that <math>(x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y)</math>. Since <math>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>.

ForThis aimplies pointthat <math>Pq</math> inis a square modulo <math>E(\mathbb{F}_{q})l</math>. satisfyingLet this,<math>q plugging\equiv itw^{2} into the\pmod characteristicl</math>. equation yields thatCompute <math>\bar{t} w\phi(Px,y) = 2\bar{q} P</math>. And consequently thatin <math>\barmathbb{tF}^{2}\bar_{q} P \equiv [x,y]/(2q)y^{2}P -x^{3}-Ax-B, \pmod psi_{l})</math>. and check whether <math>

This implies that <math>q</math> is a square modulo <math>l</math> unless <math>\bar{tq}</math> is <math>0 mod (x, y)=w\phi(x, ly)</math>. WeIf discount the latter case as it yields a contradiction. We findso, <math>q</math>'s square-roots over <math>\mathbb{F}_t_{l}</math>. Ifis <math>q \equiv w^{2}pm 2w \pmod l</math>, we find that <math>t_{l}</math> will be <math>\pm2w</math> mod <math>l</math> depending on the y-coordinate.

If <math>q</math> turns out not to be a square modulo <math>l</math> or if the equation does not hold for any of <math>w</math> and <math>-w</math>, our assumption that <math>(x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y)</math> is rendered false, forcing us to consider the case wherethus <math>(x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y)</math>,. inThe whichcharacteristic caseequation our argument asserts that <math>\bar{t}</math> isgives <math>t_l=0 \, ( mod \, l)</math>.

As you might notice, it is possible for <math>q</math> to be a square <math>\pmod l</math> but <math>(x^{q^{2}}, y^{q^{2}}) = -q(x, y)</math>. In this case however, it suffices to check whether or not either square root <math>\pm w</math> satisfies <math>\phi(P) = \pm wP</math>, for <math>P \in E[l] \setminus \{O\}</math>, and this amounts to checking whether or not <math>\gcd(numerator(x^{q}-x_{w}),\phi_{l})=1</math>. If it is <math>1</math> then we are in the minus case and <math>t_{l}=0</math>; if <math>\neq 1</math> we proceed as in the plus case with <math>t_{l}=\pm 2w</math>.

===Additional Case: <math>l = 2</math>===

Line 111 ⟶ 110:

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

(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 (cd) forto determine <math>1\leq \bar{t} \leq (l-1)/2t_l</math>; do else

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

(i) if <math>x' = x^{q} _ {\bar{t}} \pmod {\psi_{l}}</math> go to ii. . Otherwise try next value of <math>\bar{t}</math>. If you have unsuccesfully tried <math>(l-1)/2</math>, go to (d).

::(iii) if <math>(y'X -\equiv yx^{q} _ {\bar{t}})/y \equiv 0 \pmod {\psi_{l}}</math> thengo <math>t_{l}=\bar{t}</math>;to ii. . otherwiseOtherwise try next value of <math>t_{l}=-\bar{t}</math> .

::(dii)if Find <math>(y' - y^{q<} _ {\bar{t}})/math>'sy square\equiv roots0 modulo\pmod <math>{\psi_{l}}</math>,if they exist. If they don't exist then <math>t_{l}=0\bar{t}</math>.; Otherwise letotherwise <math>q\equiv w^t_{2l} =-\pmod lbar{t}</math>

:(d)Find <math>q</math>'s square roots (e) Ifmodulo <math>\gcd(numerator(x^{q}-x_{w}), \phi_{l})=1</math>,if they exist. If they don't exist then <math>t_{l}-2w=0</math>. Otherwise let <math>t_q\equiv w^{l2} \equivpmod 2wl</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.