# 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 < 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?

• It seems that you are not using the algorithm in its correct form, but in a form modified by you for reasons that are not at all clear. Presumably, your modified algorithm is not correct. – fkraiem Jan 3 '15 at 15:11
• yes I am aware of that , but if i just use algorithm as it is by doing sqrt(p) tries where p is a huge prime number then it will be worse than exhaustive searching.I know that k is a small number and I feel like I should take advantage of that – usry Jan 3 '15 at 15:16
• What are $n$ and $k$? – yyyyyyy Jan 3 '15 at 16:25
• sorry,n is same as p actually a big prime number , I edited the question. k is a upper bound we know on j hence $$j<k$$ – usry Jan 3 '15 at 16:29

To search for the values $a^x$ in the range $0 < x < 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 < 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<k$, then there will be a colliding pair $a^j = B\cdot a^{-im} = a^x \cdot a^{-im}$ with $x = j +im$
• @usry: no, what I wrote works just fine; just because you compute $a^j$ and $B \cdot a^{-im}$ modulo $p$ doesn't mess anything up. – poncho Jan 3 '15 at 17:41