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?

Improve this question
$\endgroup$
4
  • 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
    Commented Jan 3, 2015 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
    Commented Jan 3, 2015 at 15:16
  • $\begingroup$ What are $n$ and $k$? $\endgroup$
    – yyyyyyy
    Commented Jan 3, 2015 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
    Commented Jan 3, 2015 at 16:29

1 Answer 1

Reset to default
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$
2
  • $\begingroup$ Thank you.But B is again in mod p I think same issue still exists there. $\endgroup$
    – usry
    Commented Jan 3, 2015 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
    Commented Jan 3, 2015 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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