1
$\begingroup$

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!

2 Answers 2

2

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}$.

0

The algorithm requires that the group operations (and equality) are (effectively) computable. Hence multiplication is computable implies that positive powers $x^n,\ n\ge 0$ are computable. Negative powers are computable by $\:x^{-n} = (x^{-1})^n$ since the inverse operation is computable. Generally any operation derived by composing the basic operations will be computable.

In $\:\mathbb Z/m\:$ powers may be computed efficiently by repeated squaring, and inverses (of elements coprime to m) may be efficiently computed by the extended Euclidean algorithm.