Schoof's algorithm: Difference between revisions

Revision as of 19:15, 5 September 2012

Revision as of 19:23, 5 September 2012

Line 112:

==The algorithm==

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

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

:(3) for <math>l \in S</math> do:

Line 129:

:::(v)else <math>t_{l}=0</math>

::(e)else <math>t_{l}=0</math>

:(4)Use the [[Chinese Remainder Theorem]] to compute <math>\sharpt</math> E(\mathbb{F}_{q})modulo \pmod{2N}<math>N</math>.

Note that since the set <math>S</math> was chosen so that <math>2NN>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.

==Complexity of Schoof's algorithm==