Counting Points On Elliptic Curves - Baby-step Giant-step

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:

algorithm" class="article_title_2">Counting Points On Elliptic Curves - 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 ...