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.