Content deleted Content added
sp: computatio --> computation |
mostly corrections per WP:MOS and WP:MOSMATH; note that TeX in section headings fails to appear in the table of contents, so more works is needed |
||
Line 1:
'''Schoof's
The algorithm was published by René Schoof in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for [[counting points on elliptic curves]]. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and [[baby-step giant-step]] algorithms were, for the most part, tedious and had an exponential running time.
Line 6:
==Introduction==
Let <math>E</math> be an [[elliptic curve]] defined over the finite field <math>\mathbb{F}
: <math>
y^
</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_curve#The_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.
Line 14:
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]].
==Hasse's
{{main|Hasse's theorem on elliptic curves}}
Hasse's theorem states that if <math>E/\mathbb{F}_{q}</math> is an elliptic curve over the finite field <math>\mathbb{F}_{q}</math>, then <math>\sharp E(\mathbb{F}
: <math>
\mid q + 1 - \sharp E(\mathbb{F}_{q}) \mid \leq 2\sqrt{q}.
</math>
Line 26:
In order to compute <math>t \pmod l</math> for a prime <math>l \neq p</math>, we make use of the theory of the Frobenius endomorphism <math>\phi</math> and [[division polynomials]]. Note that considering primes <math>l \neq p</math> is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case <math>q=p</math> since there are more efficient, so called <math>p</math> adic algorithms for small characteristic fields.
==The Frobenius
Given the elliptic curve <math>E</math> defined over <math>\mathbb{F}_{q}</math> we consider points on <math>E</math> over <math>\overline{\mathbb{F}_{q}}</math>, the [[algebraic closure]] of <math>\mathbb{F}_{q}</math>; i.e. we allow points with coordinates in <math>\bar{\mathbb{F}}_{q}</math>. The [[Frobenius endomorphism]] of <math>\bar{\mathbb{F}}_{q}</math> over <math>\mathbb{F}
This map is the identity on <math>E(\mathbb{F}_{q})</math> and one can extend it to the point at infinity <math>O</math>, making it a [[group morphism]] from <math>E(\bar{\mathbb{F}_{q}})</math> to itself.
Line 34:
'''Theorem:''' The Frobenius endomorphism given by <math>\phi</math> satisfies the characteristic equation
: <math> \phi ^
Thus we have for all <math>P=(x, y) \in E</math> that <math>(x^{q^{2}}, y^{q^{2}} ) + q(x, y) = t(x^{q}, y^{q})</math>, where + denotes addition on the elliptic curve and <math>q(x,y)</math> and <math>t(x^{q},y^{q})</math>
Line 48:
Note that <math>\phi(O) = O</math> and that for any integer <math>r</math> we have <math>r\phi (P) = \phi (rP)</math>. Thus <math>\phi (P)</math> will have the same order as <math>P</math>. Thus for <math>(x, y)</math> belonging to <math>E[l]</math>, we also have <math>t(x^{q}, y^{q})= \bar{t}(x^{q}, y^{q})</math> if <math>t \equiv \bar{t} \pmod l</math>. Hence we have reduced our problem to solving the equation
: <math> (x^{q^{2}}, y^{q^{2}}) + \bar{q}(x, y) \equiv \bar{t}(x^{q}, y^{q}),</math>
where <math>\bar{t}</math> and <math>\bar{q}</math> have integer values in <math>[-(l-1)/2,(l-1)/2]</math>.
Line 57 ⟶ 58:
The scalar multiplication <math>\bar{q}(x, y)</math> can be done either by [[exponentiation by squaring|double-and-add]] methods or by using the <math>\bar{q}</math>th division polynomial. The latter approach gives:
: <math>
\bar{q} (x,y) = (x_{\bar{q}},y_{\bar{q}}) = \left( x - \frac {\psi_{\bar{q}-1} \psi_{\bar{q}+1}}{\psi^{2}_{\bar{q}}}, \frac{\psi_{2\bar{q}}}{2\psi^{4}_{\bar{q}}} \right)
</math>
Line 66 ⟶ 67:
We must split the problem into two cases: the case in which <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>, and the case in which <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>. Note that these equalities are checked modulo <math>\psi_l</math>.
===Case 1: <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>===
By using the [[Elliptic_curves#The_group_law|addition formula]] for the group <math>E(\mathbb{F}_{q})</math> we obtain:
: <math>
X(x,y) = \left( \frac{y^{q^{2}} - y_{\bar{q}}}{x^{q^{2}} - x_{\bar{q}}} \right) ^{2} - x^{q^{2}} - x_{\bar{q}}.
</math>
Line 79:
We first show that <math>X</math> is a function in <math>x</math> alone. Consider <math>(y^{q^{2}} - y_{\bar{q}})^{2}=y^{2}(y^{q^{2}-1}-y_{\bar{q}}/y)^{2}</math>.
Since <math>q^{2}-1</math> is even, by replacing <math>y^{2}</math> by <math>x^3+Ax+B</math>, we rewrite the expression as
: <math>
(x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))
</math>
and have that
: <math>
X(x)\equiv (x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))\bmod \psi_l(x).
</math>
Now if <math>X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x)</math> for one <math>\bar{t}\in [0,(l-1)/2]</math> then <math>\bar{t}</math> satisfies
: <math>
\phi ^{2}(P) \mp \bar{t} \phi(P) + \bar{q}P = O
</math>
for all <math>l</math>-torsion points <math>P</math>.
Line 106 ⟶ 111:
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
:(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>gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>, else <math>t_2=1</math>.
Line 128 ⟶ 133:
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
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>. By the [[prime number theorem]], we have around <math>O(\log q)</math> primes of size <math>O(\log q)</math> giving that <math>l</math> is <math>O(\log q)</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>. Given that this computation needs to be carried out for each of the <math>O(\log q)</math> primes, the total complexity of Schoof's algorithm turns out to be <math>O(\log^8 q)</math>. Note that fast polynomial arithmetic reduces the costs down to <math>O(\log^5 q)</math>.
==Improvements to Schoof's
In the 1990s, [[Noam Elkies]], followed by [[A. O. L. Atkin]], devised improvements to Schoof's basic algorithm by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime <math>l</math> is called an Elkies prime if the characteristic equation: <math>\phi^2-t\phi+ q = 0</math> splits over <math>\mathbb{F}_l</math>, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the [[
==Implementations==
Line 140 ⟶ 145:
==See also==
* [[Elliptic
* [[Counting points on elliptic curves]]
* [[Division Polynomials]]
Line 146 ⟶ 151:
==References==
* R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod p. Math. Comp., 44(170):
* R. Schoof: Counting Points on Elliptic Curves over Finite Fields. J. Theor. Nombres Bordeaux 7:
* G. Musiker: Schoof's Algorithm for Counting Points on <math>E(\mathbb{F}_{q})</math>. Available at http://www-math.mit.edu/~musiker/schoof.pdf
* A. Brown: Algorithms for Elliptic Curves over Finite Fields, EPFL
* V. Müller : Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Master's Thesis. Universität des Saarlandes, Saarbrücken, 1991. Available at http://lecturer.ukdw.ac.id/vmueller/publications.php
* A. Enge: Elliptic Curves and their Applications to Cryptography: An Introduction. Kluwer Academic Publishers, Dordrecht, 1999.
| |||