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.