Content deleted Content added
m categories |
No edit summary |
||
Line 1:
'''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 (mathematics)|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.
| |||