 Newton iteration for modular inversion

If $ax\equiv 1(\mathrm{mod}m)$, the update $x^{\prime }=x(2-ax)$ satisfies $a{x}^{\prime }\equiv 1(\mathrm{mod}{m}^2)$ because $1-a{x}^{\prime }=(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.