Thread: Modular Inversion

I have another problem from computational number theory.

Given , show how to compute by computing only one inverse and using at most multiplications.

As with my other problem, I can find faster method than computing each inverse individually, but I can't stay within the multiplication bound. My idea is this:

Let , noting that computing costs multiplications. Then, we take the inverse: . If we want to compute, say , we compute , which costs multiplications. The problem is that if is large enough, doing this procedure for all of the exceeds the limit of multiplications.

I would appreciate any suggestions for this problem.

Originally Posted by roninpro

I have another problem from computational number theory.

Given , show how to compute by computing only one inverse and using at most multiplications.

As with my other problem, I can find faster method than computing each inverse individually, but I can't stay within the multiplication bound. My idea is this:

Let , noting that computing costs multiplications. Then, we take the inverse: . If we want to compute, say , we compute , which costs multiplications. The problem is that if is large enough, doing this procedure for all of the exceeds the limit of multiplications.

I would appreciate any suggestions for this problem.

Well your method can technically fit well within the constraint, if we work in integers and rationals rather than in . (Although I doubt this is what the question poser had in mind). Consider the integer , and further the integer , all of which to obtain takes k multiplications. Now to get any requires just a single multiplication of this integer by the rational . So we use exactly 2k multiplications which is much "better" than what the problem asked for. I'm curious about better ways to do it though.