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
Other related articles:
... There are other generic algorithms for computing the order of a group element that are more space efficient, such as Pollard's rho algorithm and the Pollard kangaroo method ... The Pollard kangaroo method allows one to search for a solution in a prescribed interval, yielding a running time of, using space ...
... The best way to speed up the baby-step giant-step algorithm is to use an efficient table lookup scheme ... in O(1) time (constant time), this does not slow down the overall baby-step giant-step algorithm ...