# Knowing interval of discrete log for elliptic curve

Are there any special attacks I can apply if I know the upper bound for $n$ (meaning $0 \le n \le \text{Upper Bound}$) in the equation $Q = nP$, where $P$ is the base point and I'm trying to solve for $n$.

• How is this question different from the other one you posted 2 hours ago? (Except that it is more general, since in this case you don't mention to know the factorization of the group order).
– tylo
Apr 5, 2017 at 16:02
• @tylo As that Q was posted as an answer to his/her other question, it was converted to a comment Apr 5, 2017 at 19:21
• @user45697 It would definitely help answerers if you'ld provide some context. After all, not everyone will follow the link(s) to your previous questions. While you're at it, you could also describe your research efforts et al... to prevent answerers from repeating the obvious (which you might already know), and to help users to provide more on-point answers to your question. Thanks. Apr 5, 2017 at 19:24

As mentioned in your answer to your other similar question, Pollard's $\lambda$ algorithm is still a good choice. If your search interval is $[a,b]$, then it may find the result in $O(\sqrt{b-a})$ time using very small storage.
That "may" in the previous paragraph illustrates the trade-off you must consider. Baby step, giant step requires more memory, but it is deterministic and thus guaranteed to finish in $O(\sqrt{b-a})$ time. Pollard's $\lambda$ can be parallelized which could speed up the run time (depending on your resources), but as it's probabilistic, the run time is not guaranteed at all.
The Babystep/giantstep algorithm can find $n$ in $O(\sqrt{\text{Upper Bound}})$ time
• @user45697: unless you have significant resources, it's probably outside your budget. $O(\sqrt{\text{UB}})$ is the best you can do with a generic (group-based) attack, and so any attack will likely require at least $O(2^{50})$ point additions or equivalent; that, in itself, is likely above your budget (assuming your 'budget' is what a single laptop can do). BS/GS also requires a lot of memory; you can reduce it, but at the cost of increasing the time... Apr 5, 2017 at 16:07