Newton iteration for modular inversion
= Newton iteration for modular inversion
{c}
{title2=$x\gets x(2-ax)$}
If $ax\equiv1\pmod m$, the update $x'=x(2-ax)$ satisfies $ax'\equiv1\pmod{m^2}$ because $1-ax'=(1-ax)^2$. For odd $a$, starting with $x=1$ <modulo> $2$ and repeatedly doubling the number of correct bits computes its inverse <modulo> a <power of two>.