📐

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

1 min read

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 8ax \equiv 1 \pmod{2^3}の解.
後はHensel liftingで合っているbit数を倍々にしていけば収束する.

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

参考文献

Discussion

ログインするとコメントできます