Schoof's algorithm is an efficient algorithm to count points on elliptic curves over finite fields. The algorithm has applications in elliptic curve cryptography where it is important to know the number of points to judge the difficulty of solving the discrete logarithm problem in the group of points on an elliptic curve. 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. This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm.
Introduction Let E {\displaystyle E} be an elliptic curve defined over the finite field F q {\displaystyle \mathbb {F} _{q}} , where q = p n {\displaystyle q=p^{n}} for p {\displaystyle p} a prime and n {\displaystyle n} an integer ≥ 1 {\displaystyle \geq 1} . Over a field of characteristic ≠ 2 , 3 {\displaystyle \neq 2,3} an elliptic curve can be given by a (short) Weierstrass equation
y 2 = x 3 + A x + B {\displaystyle y^{2}=x^{3}+Ax+B}
with A , B ∈ F q {\displaystyle A,B\in \mathbb {F} _{q}} . The set of points defined over F q {\displaystyle \mathbb {F} _{q}} consists of the solutions ( a , b ) ∈ F q 2 {\displaystyle (a,b)\in \mathbb {F} _{q}^{2}} satisfying the curve equation and a point at infinity O {\displaystyle O} . Using the group law on elliptic curves restricted to this set one can see that this set E ( F q ) {\displaystyle E(\mathbb {F} _{q})} forms an abelian group, with O {\displaystyle O} acting as the zero element. In order to count points on an elliptic curve, we compute the cardinality of E ( F q ) {\displaystyle E(\mathbb {F} _{q})} . Schoof's approach to computing the cardinality # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})} makes use of Hasse's theorem on elliptic curves along with the Chinese remainder theorem and division polynomials.
Hasse's theorem
Hasse's theorem states that if E / F q {\displaystyle E/\mathbb {F} _{q}} is an elliptic curve over the finite field F q {\displaystyle \mathbb {F} _{q}} , then # E ( F q ) {\displaystyle \#E(\mathbb {F} _{q})} satisfies
∣ q + 1 − # E ( F q ) ∣≤ 2 q . {\displaystyle \mid q+1-\#E(\mathbb {F} _{q})\mid \leq 2{\sqrt {q}}.}
… excerpt ends here. Continue reading the full article.
