Schoof's algorithm: Difference between revisions

Revision as of 04:21, 19 October 2013

Revision as of 07:02, 22 October 2013

Line 10:

y^2 = x^3 + Ax + B \,

</math>

with <math>A,B\in \mathbb{F}_{q}</math>. The set of points defined over <math>\mathbb{F}_{q}</math> consists of the solutions <math>(a,b)\in\mathbb{F}_{q}^2</math> satisfying the curve equation and a [[point at infinity]] <math>O</math>. Using the [[Elliptic_curveElliptic curve#The_group_lawThe group law|group law]] on elliptic curves restricted to this set one can see that this set <math>E(\mathbb{F}_{q})</math> forms an [[abelian group]], with <math>O</math> acting as the zero element.

In order to count points on an elliptic curve, we compute the cardinality of <math>E(\mathbb{F}_{q})</math>.

Schoof's approach to computing the cardinality <math>\sharp E(\mathbb{F}_{q})</math> makes use of [[Hasse's theorem on elliptic curves]] along with the [[Chinese remainder theorem]] and [[division polynomials]].

Line 40:

denote scalar multiplication of <math>(x,y)</math> by <math>q</math> and of <math>(x^{q},y^{q})</math> by <math>t</math>.

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_curveImaginary hyperelliptic curve#Coordinate_ringCoordinate 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.

Line 68:

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

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

: <math>