**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

### Other related articles:

**Baby-step Giant-step**- Notes To The Algorithm

... 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 ...

**Baby-step Giant-step**- In Practice

... 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 ...