--- tags: 整数論 --- # Tonelli-Shanks完全に理解したい -> 理解できま(した|せんでした) ## 読んだやつ * https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm * https://github.com/kirika-comp/articles/releases/download/v1.0/seisuuron.pdf ## 草稿 ※英語版Wikipediaを訳した散文を書いて後でまとめる ### 概要 奇素数 $p$ を法として整数 $0 < n < p$ に対して $r^2 \equiv n \mod p$ を満たすような $r$ を求めるアルゴリズム ### オイラー規準 奇素数 $p$ と$p$と互いに素な $0 < a < p$ に対して $x^2 \equiv a \mod p$ を満たす $x$ があるかどうかを判定できる式、今回の $n, p$ は当然存在する方の式を満たす $a^{\frac {p-1} 2} \equiv 1 \mod p$ なら平方剰余が存在する、そうでない(左辺が-1と合同)なら存在しない(実はまだ自分で証明していないが、これを既知とします) したがって $$ n^{\frac{p-1}2} \equiv 1 \mod p $$ である 後に使う事項として $p$ 未満の正の整数( $p-1$ 個ある)のうち半分は平方剰余が存在し、残りは存在しないため適当に数字をピックすれば高い確率で好きな方を得ることが出来る(今回は存在しない方を探すのだがこれを後で使う) ### アイデア さて、 $p$ は当然奇数なので $p-1$ は偶数である、よって別の奇数 $Q$ を用いて $p-1 := Q2^S$ と書くことができる (ex. $p=13$ において $p-1 = 12 = 2^2 \times 3$ であるから $Q = 3, S=2$ ) このパラメータの内まずは$Q$を用いて次のような数$R$を考える $$ R :\equiv n^{\frac{Q+1}2} \mod p $$ これを両辺2乗すると次のようになる $$ R^2 \equiv n^{Q+1} = n \times n^Q \mod p $$ 見通しを良くするために $t :\equiv n^Q \mod p$ と定義する、するとこの式は次のようになり、解きたい式に近くなる $$ R^2 \equiv nt \mod p $$ 仮に $t \equiv n^Q \equiv 1 \mod p$ だった場合、上記のように定義した $R$ が無事に解となる、といっても一発でこのような $R$ を引くことは殆ど無いので上手くこの関係を維持したまま $R$ の変形を試みて求めたい $R$ を探す さて、この等式が満たされている時、 $M=S$ とおくと、実は $t$ は $1$ の $2^{M-1}$ 乗根である、試しに計算すると $$ t^{2^{M-1}} = t^{2^{S-1}} \equiv (n^Q)^{2^{S-1}} = n^{\frac {p-1}2} \mod p $$ オイラー規準より、この式の最右辺が1になるのは自明であり、したがって $t$ が法 $p$ の下で $1$の$2^{M-1}$ 乗根であることがわかる (※なお、 $M=S$ とわざわざ置いたのは今後 $M$ を色々変えていくので $S$ が初期パラメータであることを強調するためだと思われる(英Wikipediaではそうなっている)) ではこの * $t$ が $1$ の $2^{M-1}$ 乗根である( $0 < M \land M \in \mathbb{N}$ ) $\Leftrightarrow t^{2^{M-1}} \equiv 1 \mod p$ * $R^2 \equiv nt \mod p$ を満たすような $t, M, R$ を求めると上記の式と同じ様な関係で $t$ の位数を減らした関係を得ることが出来る これを繰り返していくと最終的に $t = 1$ の形となり、この際の $R$ が無事に平方剰余となる、これがこのアルゴリズムのコアとなるアイデアである 手順の続きだが、まず $t$ が $1$ の $2^{M-2}$ 乗根であるかを調べる( $t^{2^{M-2}} \equiv 1 \mod p$ かどうかを確かめれば良い)、仮にそうなら更に指数(の指数)を減らして同じことを試す ( $2^{M-3}, 2^{M-4}, ...$ のように続けていけば良い、なお最終的に $2^{M-M} = 1$ になった場合は無事に $t^1 \equiv 1 \mod p$ となることから $t = 1$ になる、この時の$R$が解である) もし、そうでは無い場合 $t^{2^{M-2}}$ が $-1$ となる、なぜなら $t^{2^{M-1}} \equiv 1 \mod p$ を満たす状況において $$ \sqrt {t^{2^{M-1}}} = \left(t^{2^{M-1}}\right)^{\frac 12} = t^{2^{M-2}} \equiv \pm 1 \mod p $$ であることから $1$ でない時は $-1$ のはずである ではここから上記性質を満たすように $t, M, R$ を変形していく まず $R^2 \equiv nt \mod p$ を満たすような新しいパラメータを $R', t'$ のようにおくと $R' = Rb, t' = tb^2$ のようにある数$b$を用いればこの合同式は保存される したがって $t' = tb^2$ が再び $1$ の $2^i$ 乗根(但し指数部は以前より小さくなることが要請される)となるような $b$ を用意すれば $i$ を小さくした上で同一の性質を保つことができ、再び1ずつ $i$ を減らしていくという作業に戻ることが出来る この $b$ を求める時に登場するのがオイラー規準で平方剰余と判定されなかった数である 前述の通り、これはランダムに数を取ってくるだけでも簡単に手に入るのでこれを取ってきて $z$ とおく、このような $z$ を用いて $c := z^Q$ とした $c$ は次のような性質を持つ(先程同様に $M=S$ とおいている) $$ c^{2^{M-1}} = (z^Q)^{2^{S-1}} = z^{\frac{p-1}2} \equiv -1 \mod p $$ 勿論最後の項の変形はオイラー規準によるものである。 ここで $t^{2^{i}} \equiv 1 \mod p$ であるが、 $t^{2^{i-1}} \equiv -1 \mod p$ となるような $0 < i < M$ が求まったとする このような $i$ を用いて $b := c^{2^{M-i-1}}$ とおく また、 $M$ に $i$ を代入して更新する(以後、 $M \leftarrow i$ のように書くが、数学的証明をする際に記号が被って不便なので同時に $M' = i$ のように $'$ を用いて新しい変数とする) $b$ を用いて次のように値を更新する $$ t \leftarrow tb^2 \ :(t' = tb^2) \\ R \leftarrow Rb \ :(R' = Rb) $$ このようにして入手した $t, M, R$ が要請された性質を見対しているかを確認する * $t$ が $1$ の $2^{M-1}$ 乗根である $$ t'^{2^{M'-1}} = (tb^2)^{2^{i-1}} = t^{2^{i-1}}b^{2^i} $$ ここで、 $$ b^{2^i} = \left(c^{2^{M-i-1}}\right)^{2^i} = c^{2^{M-1}} \equiv -1 $$ であり、更に $i$ が $t^{2^{i-1}} \equiv -1 \mod p$ を満たしていたことから $$ t'^{2^{M'-1}} \equiv -1^2 = 1 $$ となり、故に新たに得られた $t$ は新たに得られた $M$ を用いて $1$ の $2^{M-1}$ 乗根になることが示された * $R^2 \equiv nt \mod p$ $$ R'^2 \equiv R^2b^2 = tnb^2 = t'n \mod p $$ であるから値の更新後も $R^2 \equiv nt \mod p$ を満たす これで値の更新の前後でこの2つの性質が保存されることがわかったので後は初期条件でも成立することとこの更新が最終的に終了する、つまり $t^{2^{M-1}} = t$ となるように $M = 1$ へと辿り着き、故に $t \equiv 1 \mod p$ となることを示せば良い 前者は $Q$ を用いることで既に示されている 後者は $M$ の生成方法を考えると値の更新毎に $M$ が小さくなっていくことがわかる、つまり狭義単調減少である、そして $M$ は正の整数であるので最終的に $M=1$ へと辿り着く よってこのアルゴリズムは値の更新毎に保存される性質があり、初期条件においてその性質は満たされおり、その性質の下で無事に終了することから完全である