Baby-step Giant-step
An improvement in running time is obtained using a different approach: we pick an element by selecting random values of until is a square in and then computing the square root of this value in order to get . Hasse's theorem tells us that lies in the interval . Thus, by Lagrange's theorem, finding a unique lying in this interval and satisfying, results in finding the cardinality of . The algorithm fails if there exist two integers and in the interval such that . In such a case it usually suffices to repeat the algorithm with another randomly chosen point in .
Trying all values of in order to find the one that satisfies takes around steps.
However, by applying the baby-step giant-step algorithm to, we are able to speed this up to around steps. The algorithm is as follows.
Read more about this topic: Counting Points On Elliptic Curves