# Efficiently using BSGS or other algorithms if key range is known on Elliptic Curves

Let $$X$$ be a point on an elliptic curve such that $$X = [x]G$$, where $$G$$ is a generator. Let us assume that we know $$x$$ is something $$x = 65t + 1$$ where $$t$$ is an integer.

Now if I know that the key exist somewhere between a given range $$[A, B]$$ then which algorithm would be best to apply to find the key $$x$$?

Will it be brute-force or it will be better with BSGS or pollard-rho?

• Welcome to Cryptography.se What is the origin of this question? First of all, if you know $x = 65t + 1$ then let $x' = x -1$ and the question is now find $x'$ such that $X' = [x']G = [x]G - G$. For ranges, the Pollard's lambda ( kangaroos ) is the beast. Bruteforce newer helps for $65$ since it only reduces $6$ bits, while Pollard's rho reduced with square-root. Nov 14 at 7:43
• Of course, one can combine Pollard's lambda with the knowledge of the special form of $x$ to reduce the search to an interval of length $(B-A)/65$ (gaining 3 bits compared to Pollard's lambda in the interval $[A,B]$ itself). Nov 15 at 13:53