[Math] Baby Step Giant Step Algorithm

modular arithmetic

I'm currently trying to figure out how the Baby Step Giant Step algorithm works and there's a step which I don't really understand. (You can see it here: http://en.wikipedia.org/wiki/Baby_step_giant_step)

Basically, its step 3. where you calculate alpha^-m.

So my question is, how do you calculate the modulus of e.g. 2^-10 mod 101? I think I need the answer to be an integer in order for this algorithm to work.

Thanks a lot!

Best Answer

You calculate it as $(2^{-1})^{10}$. You calculate the inverse of $2 \pmod{101}$ by the extended euclidean algorithm, in this case it is 51, because $51 * 2 = 102 = 1 \pmod{101}$. Then you raise 51 to the power of 10 (by fast exponentiation), of course,$\mod{101}$.

Related Question