Schoof's algorithm: Difference between revisions

Revision as of 20:20, 10 May 2018

Revision as of 15:39, 21 May 2018

Line 1:

'''Schoof's algorithm''' is an efficient algorithm to count points on [[elliptic curvescurve]]s 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.