Schoof's algorithm: Difference between revisions

Revision as of 18:16, 17 March 2009

Revision as of 01:23, 20 May 2009

Line 105:

If you recall, our initial considerations omit the case of <math>l = 2</math>.

Since we assume <math>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==

Line 128 ⟶ 127:

Note that since the set <math>S</math> was chosen so that <math>2N>4\sqrt{q}</math>, by Hasse's theorem, we in fact know <math> \sharp E(\mathbb{F}_{q})</math> precisely.

==Complexity of Schoof's Algorithm==

Line 141 ⟶ 139:

* Schoof's algorithm [ftp://ftp.compapp.dcu.ie/pub/crypto/schoof2.cpp implementation] for <math>E(\mathbb{F}_{2^m})</math>.

==See Alsoalso==

* [[Elliptic Curve Cryptography ]]

* [[Counting points on elliptic curves]]

* [[Division Polynomials]]

Line 156 ⟶ 154:

* L. C. Washington: Elliptic Curves: Number Theory and Cryptography. Chapman & Hall/CRC, New York, 2003.

* N. Koblitz: A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, Springer-Verlag, 1987. Second edition, 1994

[[Category:Asymmetric-key cryptosystems]]