2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – fkraiem Jan 3 '15 at 15:11
  • $\begingroup$ 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 $\endgroup$ – usry Jan 3 '15 at 15:16
  • $\begingroup$ What are $n$ and $k$? $\endgroup$ – yyyyyyy Jan 3 '15 at 16:25
  • $\begingroup$ 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$$ $\endgroup$ – usry Jan 3 '15 at 16:29
3
$\begingroup$

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$

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thank you.But B is again in mod p I think same issue still exists there. $\endgroup$ – usry Jan 3 '15 at 15:21
  • $\begingroup$ @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. $\endgroup$ – poncho Jan 3 '15 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.