Originally Posted by

**roninpro** I have another problem from computational number theory.

Given $\displaystyle \alpha_1,\alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n$, show how to compute $\displaystyle \alpha_1^{-1}, \alpha_2^{-1}\ldots, \alpha_k^{-1}$ by computing only one inverse and using at most $\displaystyle 3k$ 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 $\displaystyle \beta=\alpha_1\alpha_2\cdots \alpha_k$, noting that computing $\displaystyle \beta$ costs $\displaystyle k-1$ multiplications. Then, we take the inverse: $\displaystyle \beta^{-1}=\alpha_1^{-1}\alpha_2^{-1}\cdots \alpha_k^{-1}$. If we want to compute, say $\displaystyle \alpha_1^{-1}$, we compute $\displaystyle \beta^{-1} \alpha_2\cdots \alpha_k=\alpha_1^{-1}$, which costs $\displaystyle k-1$ multiplications. The problem is that if $\displaystyle k$ is large enough, doing this procedure for all of the $\displaystyle \alpha_i$ exceeds the limit of $\displaystyle 3k$ multiplications.

I would appreciate any suggestions for this problem.