Question
Given $\alpha_1,\dots,\alpha_k \in \mathbb{Z}_n^\ast$, I want to compute $\alpha_1^{-1},\dots,\alpha_k^{-1}$ by computing only one multiplicative inverse and less than $3k$ multiplications modulo $n$.
Current Idea
Perform the multiplications to compute \begin{align*} A_1 &= a_1 \\ A_2 &= a_1a_2 \\ &\vdots \\ A_k &= a_1\cdots a_k \\ A_k' &= a_k \\ A_{k-1}' &= a_ka_{k-1} \\ &\vdots\\ A_{2}'&=a_k\cdots a_2. \end{align*} Since the previously computed value can be used in the multiplication for the next one, only one multiplication is used for each of the above values at most. So the total multiplications used to compute these initial values is $(k-1)+(k-2)=2k-3$.
Compute $A_k^{-1} = (a_1\cdots a_k)^{-1} \mod n$ using the Extended Euclidean algorithm.
Then $\alpha_1^{-1},\dots,\alpha_k^{-1}$ can be computed by taking \begin{align*} A_{k-1}A_k^{-1} &\equiv a_k^{-1}\\ A_{k-2}A_k^{-1}A_{k}' &\equiv a_{k-1}^{-1}\\ &\vdots\\ A_{1}A_k^{-1}A_{3}' &\equiv a_{2}^{-1}\\ A_k^{-1}A_{2}' &\equiv a_{1}^{-1} \end{align*} This however uses $2$ multiplication for each inverse except the first and last which only take one, so $2k-2$ multiplications. This totals to $4k-5$ multiplications, so I am using $k$ more multiplications than permitted. I am not sure how to remove $k$ multiplications from the total as this is the best method I have thought of. Does anyone have a suggestion on how I can improve this?
In Algorithm 10.3.4 (Parallel Inverse Modulo N) of his book A course in computational algebraic number theory, Henri Cohen gives a method (first noticed by P. Montgomery), which needs 1 Extended Euclid, plus $3k−3$ multiplications modulo $N$.