1. ## Modular Inversion

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.

2. 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.
Well your method can technically fit well within the constraint, if we work in integers and rationals rather than in $\displaystyle \mathbb{Z}_n$. (Although I doubt this is what the question poser had in mind). Consider the integer $\displaystyle \beta=\alpha_1\alpha_2\cdots \alpha_k$, and further the integer $\displaystyle \beta^{-1}\alpha_1\alpha_2\cdots \alpha_k$, all of which to obtain takes k multiplications. Now to get any $\displaystyle \alpha_i^{-1}$ requires just a single multiplication of this integer by the rational $\displaystyle \frac{1}{\alpha_i}$. 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.