= Batch modular inversion
= Single inversion trick
{synonym}
= Batch inversion
{synonym}
For invertible <residue classes> $a_1,\ldots,a_n$, all their <modular inverses> can be recovered with one inversion and a linear number of multiplications. Store prefix products $P_i=a_1\cdots a_i$, invert $P_n$ once, and sweep backward: if the current inverse is $P_i^{-1}$, then $a_i^{-1}=P_i^{-1}P_{i-1}$ and $P_{i-1}^{-1}=P_i^{-1}a_i$. The same construction works in any commutative <group>.
Back to article page
