Garnerのアルゴリズム

この記事ではGarnerのアルゴリズムの「気持ち」を説明します。
アルゴリズムの説明のみであり、実装については一切説明していません。
合同式の取扱にある程度慣れていることを前提とします（「適当な条件の下ではmodをとっても加減乗除ができる」と知っているくらい）
本質ポイントがたくさんあるのでちょっと説明が難しい。

以下変数は全て非負であるとする。
非負整数kと正整数mに対して、x=kmodm$x=k\mathrm{mod}m$を満たす最小の非負整数xをk%m$k\mathrm{\%}m$と略記する。（要はC言語などの普通の剰余演算）

・Garnerのアルゴリズムとは
x%mi=λi$x\mathrm{\%}{m}_i={\lambda }_i$　というn個の合同式と正整数M$M$が与えられる。
mi$m_i$たちは互いに素(pairwise coprime)である。
このとき、この連立合同式の非負整数解xであって、最小のものについて、x%M$x\mathrm{\%}M$を求めることができる。
（方程式のindexは1-basedとする）

・ちょっと意味がわからん
例題
x%3=2x%5=3x%7=2$$\begin{gathered} x\mathrm{\%}3=2 \\ x\mathrm{\%}5=3 \\ x\mathrm{\%}7=2 \end{gathered}$$
を満たす最小の非負整数xについてx%11を求めよ

・気持ちの整理
本質ポイント１：前から貪欲に計算できる
例題を考えよう。
2つ目の条件までについてx%15=8$x\mathrm{\%}15=8$であれば良いことがわかっているとして、これを満たし、かつx%7=2$x\mathrm{\%}7=2$となるようなものを探すにはどうすればよいか。
この問題に答えるのは簡単でx=8+15k$x=8+15k$という形であってx%7=2$x\mathrm{\%}7=2$になるものを探せば良い。これは1変数の合同式なので容易に(O(log m_i)で)解ける。
このことから、前から順番に方程式を解決していくことで、x=k1+k2m1+k3m1m2+…modm1m2…$x=k_1+k_2{m}_1+k_3{m}_1{m}_2+\dots \mathrm{mod}{m}_1{m}_2\dots$という形で、ki$k_i$を前から順に決めていくことが出来ることがわかる。
本質ポイント２：この方法で最小解が求まる
つまり上の例で言えば、合同式としての解はk=1mod7$k=1\mathrm{mod}7$と求まるわけだが、最小解はk=1$k=1$のときに達成されるということ。
中国剰余定理を用いて証明できる。

・Garner法の気持ち
i-1番目までの方程式から定まるあるai,bi$a_i,b_i$によって記述される方程式ai+bi∗ki=λimodmi$a_i+b_i\ast k_i={\lambda }_i\mathrm{mod}{m}_i$を解くことでki$k_i$たちは求めることができるということはわかった。
本質ポイント３：これはmodmi$\mathrm{mod}{m}_i$の世界の話だから、ai,bi$a_i,b_i$がmodmi$\mathrm{mod}{m}_i$で求まればよい。
実際、bi=∏i−1j=1mj$b_i=\prod _{j=1}^{i-1}{m}_j$、ai=∑i−1j=1kjbj$a_i=\sum _{j=1}^{i-1}{k}_j{b}_j$であることからこれは容易に計算できる。
ki$k_i$たちさえ計算できてしまえば、最小解はx=an+1$x=a_{n+1}$なので、これのMでの剰余を計算すればよい。