Finding discrete logarithm with baby-step-giant-step algorithm I am trying to use the Baby Step Giant Step algorithm to find discrete logarithm in:
$$a^x= B  \pmod p$$
with using BSGS:
$$x = im+j$$ 
$$a^j = B a^{-im}$$ where 
$m = \sqrt{p}$

Wikipedia says: 


  A cyclic group of order $p$, having a generator $\alpha$ and an element $B$.


But $p$ is a 158 bit number. Hence $m$ is too large and I know that $j$ is not a very big number,  $j &lt; k$, where $k \ll n$.
I try to limit test values for $j$ and $i$ by defining $n$ as the next prime of $k$, but in this case I have this problem:

$$x = im+j \pmod {\operatorname{nextPrime}(k)}$$

$$a^x = B\pmod p$$
and when I try $B a^{-im}$ it does not give me $a^j$  because $B$ is actually $a^x \pmod p$ and I cannot find it in the lookup table I have created using values of $a^j$.

How can I solve this?
To search for the values $a^x$ in the range $0 &lt; x &lt; k$, what you need to do is set $m = \sqrt{k}$ (rounded up), and then do the Baby Step/Giant Step algorithm for $0 \le i, j &lt; m$.

That is, you generate the values $a^0, a^1, ..., a^{m-1}$ and the values $B\cdot a^{-0}, B\cdot a^{-m}, B\cdot a^{-2m}, ..., B\cdot a^{-(m-1)m}$; if $x&lt;k$, then there will be a colliding pair $a^j = B\cdot a^{-im} = a^x \cdot a^{-im}$ with $x = j +im$