Content deleted Content added
→Computation modulo primes: there was a 2 missing in the formula for calculation qbar(x,y) with division polynomials. source: http://www-math.mit.edu/~musiker/schoof.pdf |
m small syntax problem in a latex formula |
||
Line 108:
==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 > 2\sqrt{q}.</math>
:(2) put <math>t_2=0</math> if <math>
:(3) 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>
Line 126:
:(4)Use the Chinese Remainder Theorem to compute <math>\sharp E(\mathbb{F}_{q}) \pmod{2N}</math>.
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==
| |||