# Modular Inversion

• Aug 27th 2010, 07:47 PM
roninpro
Modular Inversion
I have another problem from computational number theory.

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

I would appreciate any suggestions for this problem.
• Aug 27th 2010, 09:51 PM
undefined
Quote:

Originally Posted by roninpro
I have another problem from computational number theory.

Given $\alpha_1,\alpha_2,\ldots, \alpha_k\in \mathbb{Z}_n$, show how to compute $\alpha_1^{-1}, \alpha_2^{-1}\ldots, \alpha_k^{-1}$ by computing only one inverse and using at most $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 $\beta=\alpha_1\alpha_2\cdots \alpha_k$, noting that computing $\beta$ costs $k-1$ multiplications. Then, we take the inverse: $\beta^{-1}=\alpha_1^{-1}\alpha_2^{-1}\cdots \alpha_k^{-1}$. If we want to compute, say $\alpha_1^{-1}$, we compute $\beta^{-1} \alpha_2\cdots \alpha_k=\alpha_1^{-1}$, which costs $k-1$ multiplications. The problem is that if $k$ is large enough, doing this procedure for all of the $\alpha_i$ exceeds the limit of $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 $\mathbb{Z}_n$. (Although I doubt this is what the question poser had in mind). Consider the integer $\beta=\alpha_1\alpha_2\cdots \alpha_k$, and further the integer $\beta^{-1}\alpha_1\alpha_2\cdots \alpha_k$, all of which to obtain takes k multiplications. Now to get any $\alpha_i^{-1}$ requires just a single multiplication of this integer by the rational $\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.