Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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