Content deleted Content added
Line 133:
==Complexity of Schoof's Algorithm==
Most of the computation is taken by the evaluation of <math>\phi(P)</math> and <math>\phi^{2}(P)</math>, for each prime <math>l</math>, that is computing <math>x^q</math>, <math>y^q</math>, <math>x^{q^2}</math>, <math>y^{q^2}</math> for each prime <math>l</math>. This involves exponentiation in the ring <math>R = \mathbb{F}_{q}[x, y]/ (y^2-x^3-Ax-B, \psi_l)</math> and requires <math>O(\log q)</math> multiplications. Since the degree of <math>\psi_l</math> is <math>\frac{l^2-1}{2}</math>, each element in the ring is a polynomial of degree <math>O(l^2)</math>, and we obtain that <math>O(l^2) = O(\log^2q)</math>. Thus each multiplication in the ring <math>R</math> requires <math>O(\log^4 q)</math> multiplications in <math>\mathbb{F}_{q}</math> which in turn requires <math>O(\log^2 q)</math> bit operations. In total, the number of bit operations for each prime <math>l</math> is <math>O(\log^7 q)</math>. By the [[prime number theorem
==Improvements to Schoof's Algorithm==
| |||