gcd(a, 2)=1であるaに対するax≡1 (mod 2^k)の効率的な求め方

TL;DR

$x_0=a \bmod 8$として$x_{n+1}=2x_n-ax_n^2 \bmod 2^k$ が収束するまで反復すれば良い.

解説

$\gcd(a, 2)=1$より、$a$は奇数. ここで$(4n\pm 1)^2=16n^2\pm 8n+1\equiv 1 \pmod{8}$より, $a \bmod 8$は$ax \equiv 1 \pmod{2^3}$の解.
後はHensel liftingで合っているbit数を倍々にしていけば収束する.

誤り等あればコメントで教えて下さい。

参考文献

https://www.asakura.co.jp/detail.php?book_code=11128
https://en.wikipedia.org/wiki/Montgomery_modular_multiplication