下記が成り立ちます。 $$ \begin{aligned} &\phantom{{}={}} 6259918212890625^2 \\ &= 39186576032079756259918212890625 \\ &\equiv 6259918212890625 \pmod{10^{16}}. \end{aligned} $$ 今日はこういう感じのやつを求めていきます。
方法①
与えられた $k$ に対して $x^2 \equiv x \pmod{10^k}$ を満たす $0\le x\lt 10^k$ について考えます。 $10^k = 2^k\cdot 5^k$ であり、$2$ と $5$ が素数であることから $$ \begin{cases} x\equiv 0 \vee x\equiv 1 \pmod{2^k}, \\ x\equiv 0 \vee x\equiv 1 \pmod{5^k} \end{cases} $$ です。
中国剰余定理を踏まえつつ各ケースについて考えていきます。
$$ \begin{cases} x\equiv 0 \pmod{2^k}, \\ x\equiv 0 \pmod{5^k} \\ \end{cases} $$ のとき、ある $q\in\N$ が存在して $x = q\cdot 2^k+0$ と書け、$q\cdot 2^k\equiv 0\pmod{5^k}$ です。 $\gcd(2, 5) = 1$ なので $q\equiv 0\pmod{5^k}$ です。よって $q = 0$ や $x = 0$ が従います。
$$ \begin{cases} x\equiv 1 \pmod{2^k}, \\ x\equiv 1 \pmod{5^k} \\ \end{cases} $$ のとき、ある $q\in\N$ が存在して $x = q\cdot 2^k+1$ と書け、$q\cdot 2^k + 1\equiv 1\pmod{5^k}$ です。 同様にして $x = 1$ が従います。
$$ \begin{cases} x\equiv 1 \pmod{2^k}, \\ x\equiv 0 \pmod{5^k} \\ \end{cases} $$ のとき、ある $q\in\N$ が存在して $x = q\cdot 2^k+1$ と書け、$q\cdot 2^k+1\equiv 0\pmod{5^k}$ です。 $q\equiv (-1)\cdot (2^{-k}) \pmod{5^k}$ より、$x = (-2^{-k}\bmod{5^k})\cdot 2^k + 1$ となります。
$$ \begin{cases} x\equiv 0 \pmod{2^k}, \\ x\equiv 1 \pmod{5^k} \\ \end{cases} $$ のとき、同様にして $x = (-5^{-k}\bmod{2^k})\cdot 5^k + 1$ となります。
>>> (lambda k: (-pow(2, -k, 5**k) * 2**k + 1) % 10**k)(64) 9580863811000557423423230896109004106619977392256259918212890625 >>> (lambda k: (-pow(2, -k, 5**k) * 2**k + 1) % 10**k)(64)**2 % 10**64 9580863811000557423423230896109004106619977392256259918212890625
ということで、競プロ界隈でも比較的有名そうな知識（主観）で簡単に求まってしまいました。 元々は、比較的有名ではなさそう（主観）な別の方法で求めるのを記事にしようと思っていたのですが、そっかーという感じになりました。
方法②
元々考えていた方法はこちらです。
Newton 法というのがあります。大学や基本情報技術者試験などで学びがちな Newton 法は数値計算の文脈のものが多く、たとえば $\sqrt2$ の近似値を求めるようなときに使いがちな気がします。 それに限らず、一般の環においての定理があります。
環 $R$ を考えます。$R$ 係数で不定元を $y$ とする多項式全体からなる集合を $R[y]$ と書きます。 $m\in R$ かつ $\varphi\in R[y]$ とし、$g\in R$ が $\varphi(g)\equiv 0\pmod{m}$ が成り立ち、さらに $\varphi'(g)^{-1}\bmod m$ が存在するとします*1。 このとき、 $$ h = \left(g - \varphi(g)\cdot \varphi'(g)^{-1}\right) \bmod {m^2} $$ で定義すると、$\varphi(h) \equiv 0 \pmod{m^2}$ かつ $h \equiv g \pmod{m}$ が成り立ち、さらに $\varphi'(h)^{-1}\bmod m^2$ が存在します。
証明については Modern Computer Algebra[1] の Lemma 9.21 などを見ましょう。
ということで、$\varphi = y^2 - y \in \Z[y]$ で定義して $\varphi(g) \equiv 0\pmod{10^k}$ なる $g$ を求めたいということになります。 $\varphi(g) \equiv 0\pmod{10^j}$ なる $g$ が求められているとき、 $$ \begin{aligned} h &\equiv g - (g^2 - g)\cdot (2g-1)^{-1} \\ &\equiv (g\cdot(2g-1) - (g^2 - g) )\cdot (2g-1)^{-1} \\ &\equiv (2g^2-g-g^2+g)\cdot (2g-1)^{-1} \\ &\equiv g^2 \cdot (2g-1)^{-1} \pmod{10^{2j}} \end{aligned} $$ として $\varphi(h)\equiv 0\pmod{10^{2j}}$ なる $h$ が求められます。
def newton(g, m, k): for _ in range(k): m *= m g = g**2 * pow(2 * g - 1, -1, m) % m return g
$\varphi(5)\equiv 0 \pmod{10}$ は既知として、たとえば newton(5, 10, 6) を呼び出すと、g が
25 625 12890625 6259918212890625 4106619977392256259918212890625 9580863811000557423423230896109004106619977392256259918212890625
といったように収束していく様子が見られます。
他にも Halley 法というのがあり、こちらは三次収束です。
def halley(g, m, k): for _ in range(k): m *= m * m g = g**3 * pow(3 * g**2 - 3 * g + 1, -1, m) % m return g
625 212890625 619977392256259918212890625 938509890062166509580863811000557423423230896109004106619977392256259918212890625
反復回数としては Halley 法の方が $\log_3(2)\approx 0.63$ 倍だけ得していますが、反復ごとの計算は Newton 法の方が単純がちなので、Newton 法の方が結局は得していそうな気がします*2。
もちろん、$x^3 \equiv x \pmod{10^k}$ のような式を満たす $x$ についても（どちらの方法でも）求められます。
$$ \begin{aligned} &\phantom{{}={}} 6259918212890624^3 \\ &= 245304761004039189166825963184256259918212890624 \\ &\equiv 6259918212890624 \pmod{10^{16}}. \end{aligned} $$
おまけ
“Newton’s method Codeforces” でググったところ下記の記事が上位に出てきました。競プロ界隈で Newton 法と言えば数値計算ではなく FPS の文脈がちで、偏ってるな〜と面白くなりました。
- CDQ convolution (online FFT) generalization with Newton method by adamant
- Operations on Formal Power Series by rng_58
- A problem collection of ODE and differential technique by jqdai0815
そういえば、自分も過去になんかを書いていたらしいです。記憶から抜けていました。
経緯
今回は YouTube の動画に触発されたシリーズです。
他の回としては下記のようなものがあります。
別にわざわざ書く必要もないか？みたいな気持ちになりながらも一応書きました。
twitter.com「A というトピックについて考えましょう」
— えびちゃん🍑🍝🦃 (@rsk0315_h4x) 2025年12月5日
「これは界隈にはあまり浸透していない B 法で求められます、おもしろーい」
「あれ、界隈に浸透している C 法で求められますね、つまんなーい」
みたいになり投げ出してしまいました、もったいなーい
ところで、CRT と言えば最近は No.3396 ChRisTmas memory がアツいらしいです？
参考文献
[1]: Gathen, Joachim von zur, and Jürgen Gerhard. Modern Computer Algebra. 3rd ed. Cambridge: Cambridge University Press, 2013.
あとがき
前回の記事から間隔が空いてしまいました。いろいろなコンテンツに手を出していて、あまり記事を書こうという感じになっていませんでした。
CTF で crypto とかをしていると word size に収まらないような数が当然のように出てくるので、競プロ界隈とは違った感じがするな〜という気持ちになります。 Daily AlpacaHack などが最近の初心者向けコンテンツとしてはよさそうなのかな〜と思ったりしています。
それはそれとして、word size の高速素因数分解とかも興味はありますよね。SQUFOF のお勉強もしなきゃなと思っています。
おなかがすきました。気持ちや頭の中が無のときにあとがきを書くと短めになることがわかりました。
おわり
おわりましょう。
