Does knowing that the exponent is in a certain range help solving discrete log? given:
$c=g^i \bmod P$
$g$ generator for group with group size $\varphi(P)$
$g,P,\varphi(P)$,c is known by the attacker
He wants to know $i$.

Now the attacker also knows $j,k$ with $j&lt;i&lt;k$
$k-j$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $i$ help the attacker?
The basic baby-step-giant-step algorithm can be tweaked to make use of this information.
The following algorithm takes $\Theta(\!\sqrt{k-j})$ group operations.


Let $h:=c\cdot g^{-j-1}$, which equals $g^{i-j-1}$.
Pick some integer $m\geq\sqrt{k-j-1}$.
Initialize an empty lookup table $T$.
For all $0\leq a&lt;m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$.
For all $0\leq b&lt;m$, compute $g^{-b}h$ and check if $g^{-b}h$ is in $T$. When a match is found, return $j+1+m\cdot T[g^{-b}h]+b$.


Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $i$ by $i-j-1$ in step 1 and adjusting the output accordingly in step 5.



Correctness:
If the algorithm returns something, it must be of the form $r=j+1+m\alpha+\beta$ with $0\leq\alpha,\beta&lt;m$ and $T[g^{-\beta}h]=T[g^{m\alpha}]$.
This implies
$$
g^r
= g^{j+1+m\alpha+\beta}
= g^{j+1-\beta+(i-j-1)+\beta}
= g^i
\text,
$$
hence $r=i$ (modulo the order of $g$).

Completeness: Let $b:=(i-j-1)\bmod m$ and $a:=(i-j-1-b)/m$.
These values are in the range $0\leq a,b&lt;m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.