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

公開:2021/01/02
更新:2021/01/02
1 min読了の目安(約300字TECH技術記事

TL;DR

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

解説

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

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

参考文献