中国剰余定理

xとy が両方ともすべての合同式の解であると仮定します。xとyをn _iで割ったときの余りが同じであるため、それらの差x − yは各n _iの倍数になります。n i は互いに素であるため、_それらの積Nもx − yを割り切るため、xとyはN を法として合同です。xとyが 非負でNより小さいと仮定する場合(定理の最初の記述のように)、それらの差がNの倍数になるのはx = yの場合のみです。

地図

${\displaystyle x{\bmod {N}}\mapsto (x{\bmod {n}}_{1},\ldots ,x{\bmod {n}}_{k})}$

この写像は、Nを法とする合同類をn _iを法とする合同類の列に写像します。一意性の証明は、この写像が単射であることを示しています。この写像の定義域と値域は同じ数の要素を持つため、この写像は全射でもあり、解の存在が証明されます。

この証明は非常に単純ですが、解を直接計算する方法は提供していません。さらに、この証明は、以下の証明が適用可能な他の状況に一般化することはできません。

xの存在は、明示的な構成によって確立される可能性がある。^{[ 16 ]}この構成は、まず 2 つのモジュライの場合の問題を解決し、次にモジュライの数に関する帰納法によってこの解決策を一般の場合に拡張するという 2 つのステップに分割できる。

解を構築するにあたって、法の数に関する帰納法を用いる必要はありません。しかしながら、このような直接的な構築法は、大きな数値を用いた計算量が多くなるため、効率が悪く、あまり用いられません。とはいえ、ラグランジュ補間は、整数ではなく多項式に適用される、この構築法の特殊なケースと言えます。

させて${\displaystyle N_{i}=N/n_{i}}$1つを除くすべてのモジュラスの積となる。${\displaystyle n_{i}}$互いに素であり、${\displaystyle N_{i}}$そして${\displaystyle n_{i}}$互いに素である。したがってベズーの恒等式が適用され、整数が存在する。${\displaystyle M_{i}}$そして${\displaystyle m_{i}}$そのため

${\displaystyle M_{i}N_{i}+m_{i}n_{i}=1.}$

合同式の解は

${\displaystyle x=\sum _{i=1}^{k}a_{i}M_{i}N_{i}.}$

実際、${\displaystyle N_{j}}$の倍数です${\displaystyle n_{i}}$のために${\displaystyle i\neq j,}$ 我々は持っています

${\displaystyle x\equiv a_{i}M_{i}N_{i}\equiv a_{i}(1-m_{i}n_{i})\equiv a_{i}{\pmod {n_{i}}},}$

すべての${\displaystyle i.}$

xの値が解であるかどうかを確認するのは簡単です。xを各n _iでユークリッド除算したときの余りを計算すれば十分です。したがって、解を見つけるには、解が見つかるまで0からNまでの整数を順に調べていけばよいのです。

この方法は非常に単純ですが、非常に非効率的です。ここで検討した単純な例では、解である39を見つけるために40 個の整数 ( 0を含む) をチェックする必要があります。これは指数時間アルゴリズムであり、入力のサイズは定数倍を除いてNの桁数であり、平均演算回数はNのオーダーです。

そのため、この方法は手書き計算においてもコンピュータ上でもほとんど用いられていない。

ふるい分けによって解の探索を劇的に速くすることができる。この方法では、一般性を失うことなく、次のことを仮定する。$0\leq a_{i}<n_{i}}$（そうでない場合は、それぞれを交換するだけで十分です）${\displaystyle a_{i}}$残りの分割によって${\displaystyle n_{i}}$これは、解が等差数列に属することを意味する。

${\displaystyle a_{1},a_{1}+n_{1},a_{1}+2n_{1},\ldots }$

これらの数値の値をモジュロでテストすることにより${\displaystyle n_{2},}$最終的には解決策が見つかる${\displaystyle x_{2}}$最初の2つの合同式のうち、解は等差数列に属する。

${\displaystyle x_{2},x_{2}+n_{1}n_{2},x_{2}+2n_{1}n_{2},\ldots }$

これらの数値の値をモジュロでテストします${\displaystyle n_{3},}$そして、すべてのモジュラスがテストされるまで続けると、最終的に解が得られる。

この方法は、モジュラスが降順で並べられている場合、つまり${\displaystyle n_{1}>n_{2}>\cdots >n_{k}.}$例として、次の計算を行います。まず、4を法とする5（最大の法）で合同な数、すなわち4、9 = 4 + 5、14 = 9 + 5 、…を考えます。それぞれの数について、4（2番目に大きい法）による余りを計算し、3を法とする4で合同な数が得られるまで続けます。次に、各ステップで20 = 5 × 4を加え、3による余りのみを計算します。これにより、次のようになります。

4 mod 4 → 0。続行

4 + 5 = 9 mod 4 → 1。続く

9 + 5 = 14 mod 4 → 2。続く

14 + 5 = 19 mod 4 → 3。よし、剰余を 3 で計算し、毎回 5 × 4 = 20 を加えることで続けよう。

19 mod 3 → 1. 続行

19 + 20 = 39 mod 3 → 0。よし、これが結果だ。

この方法は、法の積がそれほど大きくない手書き計算には適しています。しかし、法の積が非常に大きい場合、他の方法に比べてはるかに遅くなります。系統的探索よりは劇的に高速ですが、この方法も指数関数的な時間計算量を持つため、コンピュータでは使用されません。

構成的存在証明は、2 つの法の場合、解は法のベズー係数を計算し、その後、法を法とするいくつかの乗算、加算、減算を行うことで得られることを示している。${\displaystyle n_{1}n_{2}}$（区間内の結果を得るため）${\displaystyle (0,n_{1}n_{2}-1)}$) ベズー係数は拡張ユークリッドアルゴリズムで計算できるため、全体の計算時間は最大で2次になります。${\displaystyle O((s_{1}+s_{2})^{2}),}$どこ${\displaystyle s_{i}}$は桁数を表します${\displaystyle n_{i}.}$

法が2つを超える場合、2つの法の場合と同様に、任意の2つの合同式を、それらの法の積を法とする1つの合同式に置き換えることができます。このプロセスを繰り返すことで、最終的に解が得られます。その計算量は、すべての法の積の桁数に対して2乗となります。この2乗の時間計算量は、法を再グループ化する順序には依存しません。最初の2つの法を再グループ化し、その結果得られた法を次の法と再グループ化するというように、繰り返して計算できます。この方法は実装が最も簡単ですが、大きな数値を扱う計算量も多くなります。

別の戦略としては、法を積の大きさが（可能な限り）同程度になるようにペアに分割し、各ペアに対して2法法を並列に適用し、法の数を2で割った値で反復するという方法がある。この方法により、アルゴリズムの並列化が容易になる。また、基本演算に高速アルゴリズム（すなわち、準線形時間で動作するアルゴリズム）を使用すれば、この方法によって計算全体を準線形時間で処理できるアルゴリズムが得られる。

今回の例（モジュラスが3つしかない）では、どちらの戦略も同一であり、以下のように機能します。

3と4のベズーの恒等式は

${\displaystyle 1\times 4+(-1)\times 3=1.}$

これを存在証明の公式に代入すると、

${\displaystyle 0\times 1\times 4+3\times (-1)\times 3=-9}$

最初の2つの合同式の解は、−9に3×4=12の任意の倍数を加えることで得られます。これらの解のいずれを使用しても構いませんが、解3=−9+12は（絶対値が）小さいため、おそらく計算が容易になります。

5と3×4=12のベズー恒等式は

${\displaystyle 5\times 5+(-2)\times 12=1.}$

同じ公式を再度適用すると、問題の解が得られます。

${\displaystyle 5\times 5\times 3+12\times (-2)\times 4=-21.}$

他の解は、3 × 4 × 5 = 60の任意の倍数を加えることで得られ、最小の正の解は−21 + 60 = 39です。

中国剰余定理によって解かれる合同式の系は、線形ディオファントス方程式の系として書き直すことができる。

${\displaystyle {\begin{aligned}x&=a_{1}+x_{1}n_{1}\\&\vdots \\x&=a_{k}+x_{k}n_{k},\end{aligned}}}$

ここで未知の整数は${\displaystyle x}$そして${\displaystyle x_{i}.}$したがって、このようなシステムを解くための一般的な方法はすべて、システムの行列をスミス標準形やエルミート標準形に変換するなど、中国剰余定理の解を求めるために使用できます。ただし、一般的なアルゴリズムをより具体的な問題に適用する場合によくあるように、この方法は、ベズーの恒等式を直接使用する前のセクションの方法よりも効率が劣ります。

多項式に対する中国剰余定理の特殊なケースとして、ラグランジュ補間があります。このために、次数1のk個の単項式を考えます。

${\displaystyle P_{i}(X)=X-x_{i}.}$

ペアワイズ互いに素であるのは、${\displaystyle x_{i}}$すべて異なります。${\displaystyle P_{i}(X)}$多項式の${\displaystyle P(X)}$は${\displaystyle P(x_{i})}$多項式の剰余定理により。

さあ、${\displaystyle A_{1},\ldots ,A_{k}}$定数（次数0の多項式）${\displaystyle K.}$ラグランジュ補間と中国剰余定理はどちらも一意の多項式の存在を主張する${\displaystyle P(X),}$次数が${\displaystyle k}$そのため

${\displaystyle P(x_{i})=A_{i},}$

すべての${\displaystyle i.}$

ラグランジュ補間公式は、この場合、上記の解の構成の結果に他ならない。より正確には、

${\displaystyle {\begin{aligned}Q(X)&=\prod _{i=1}^{k}(X-x_{i})\\[6pt]Q_{i}(X)&={\frac {Q(X)}{X-x_{i}}}.\end{aligned}}}$

部分分数分解${\displaystyle {\frac {1}{Q(X)}}}$は

${\displaystyle {\frac {1}{Q(X)}}=\sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}.}$

実際、右辺を共通分母に簡約すると、

${\displaystyle \sum _{i=1}^{k}{\frac {1}{Q_{i}(x_{i})(X-x_{i})}}={\frac {1}{Q(X)}}\sum _{i=1}^{k}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}},}$

分子は 1 に等しく、次数が 未満の多項式である。${\displaystyle k,}$これは、1 の値をとります${\displaystyle k}$異なる値${\displaystyle X.}$

上記の一般式を用いると、ラグランジュ補間式が得られます。

${\displaystyle P(X)=\sum _{i=1}^{k}A_{i}{\frac {Q_{i}(X)}{Q_{i}(x_{i})}}.}$

エルミート補間は、1変数多項式に対する中国剰余定理の応用であり、任意の次数の法を扱うことができる（ラグランジュ補間は次数1の法のみを扱う）。

この問題は、ある固定点において、多項式とその1階導関数が与えられた値をとるような、次数が最小の多項式を見つけることである。

より正確には、${\displaystyle x_{1},\ldots ,x_{k}}$なれ${\displaystyle k}$地盤の要素${\displaystyle K,}$そして、${\displaystyle i=1,\ldots ,k,}$させて${\displaystyle a_{i,0},a_{i,1},\ldots ,a_{i,r_{i}-1}}$最初の値${\displaystyle r_{i}}$求める多項式の導関数${\displaystyle x_{i}}$（0次導関数、つまり多項式自体の値を含む）。問題は、多項式を見つけることです。${\displaystyle P(X)}$j階導関数が次の値をとる${\displaystyle a_{i,j}}$で${\displaystyle x_{i},}$のために${\displaystyle i=1,\ldots ,k}$そして${\displaystyle j=0,\ldots ,r_{j}.}$

多項式を考える

${\displaystyle P_{i}(X)=\sum _{j=0}^{r_{i}-1}{\frac {a_{i,j}}{j!}}(X-x_{i})^{j}.}$

これは次数 のテイラー多項式です${\displaystyle r_{i}-1}$で${\displaystyle x_{i}}$未知の多項式の${\displaystyle P(X).}$したがって、私たちは

${\displaystyle P(X)\equiv P_{i}(X){\pmod {(X-x_{i})^{r_{i}}}}.}$

逆に、任意の多項式${\displaystyle P(X)}$これらを満たす${\displaystyle k}$合同式、特に検証する式は、任意の${\displaystyle i=1,\ldots ,k}$

${\displaystyle P(X)=P_{i}(X)+o(X-x_{i})^{r_{i}-1}}$

したがって${\displaystyle P_{i}(X)}$次数 のテイラー多項式は${\displaystyle r_{i}-1}$で${\displaystyle x_{i}}$つまり、${\displaystyle P(X)}$初期のエルミート補間問題を解決します。中国剰余定理は、次数が和より小さい多項式がちょうど 1 つ存在すると主張します。${\displaystyle r_{i},}$これらの条件を満たす${\displaystyle k}$合同関係。

解を計算する方法はいくつかあります${\displaystyle P(X).}$§ 単変数多項式環とユークリッド領域について の冒頭で説明した方法を用いることができます。また、 § 存在 (構成的証明)または§ 存在 (直接証明)で示されている構成を用いることもできます。

させて${\displaystyle I_{1},I_{2},\dots ,I_{k}}$互いに素な両側イデアルである${\displaystyle \bigcap _{i=1}^{k}I_{i}=0,}$そして

${\displaystyle \varphi :R\to (R/I_{1})\times \cdots \times (R/I_{k})}$

上記で定義した同型写像をとする。${\displaystyle f_{i}=(0,\ldots ,1,\ldots ,0)}$要素である${\displaystyle (R/I_{1})\times \cdots \times (R/I_{k})}$その構成要素は、i番目の要素を除いてすべて0であり、i番目の要素は1である。${\displaystyle e_{i}=\varphi ^{-1}(f_{i}).}$

の${\displaystyle e_{i}}$これらは互いに直交する中心冪等元です。これは特に、${\displaystyle e_{i}^{2}=e_{i}}$そして${\displaystyle e_{i}e_{j}=e_{j}e_{i}=0}$すべてのiとjに対して。さらに、${\textstyle e_{1}+\cdots +e_{n}=1,}$そして${\displaystyle I_{i}=R(1-e_{i}).}$

要約すると、この一般化された中国剰余定理は、互いに素で共通部分がゼロである両側イデアルを与えることと、合計が1になる中心的かつ互いに直交する冪等元を与えることの等価性である。^{[ 20 ]}

中国剰余定理は、数列のゲーデル番号付けを構築するために使用されており、これはゲーデルの不完全性定理の証明に関係している。

素因数FFTアルゴリズム（グッド・トーマスアルゴリズムとも呼ばれる）は、中国剰余定理を用いて、サイズの高速フーリエ変換の計算量を削減します。${\displaystyle n_{1}n_{2}}$より小さなサイズの 2 つの高速フーリエ変換の計算${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$（ただし、${\displaystyle n_{1}}$そして${\displaystyle n_{2}}$互いに素である）。

RSAのほとんどの実装では、 HTTPS証明書の署名時と復号時に中国剰余定理が用いられています。

中国剰余定理は、秘密分散にも利用できます。秘密分散とは、ある一連のシェアを複数の人に分配し、全員が協力すれば（ただし、一人では不可能）、そのシェアの集合から特定の秘密を復元できるというものです。各シェアは合同式で表され、中国剰余定理を用いた合同式の解が復元すべき秘密となります。中国剰余定理を用いた秘密分散では、中国剰余定理に加えて、ある一定の濃度未満のシェアの集合から秘密を復元することが不可能であることを保証する特別な整数列が使用されます。

中パルス繰り返し周波数レーダーで使用される距離曖昧性解消技術は、中国剰余定理の特殊なケースと見なすことができる。

全射が与えられた場合${\displaystyle \mathbb {Z} /n\to \mathbb {Z} /m}$有限アーベル群の場合、中国剰余定理を使用して、そのような写像を完全に記述することができます。まず、この定理は同型写像を与えます。

${\displaystyle {\begin{aligned}\mathbb {Z} /n&\cong \mathbb {Z} /p_{n_{1}}^{a_{1}}\times \cdots \times \mathbb {Z} /p_{n_{i}}^{a_{i}}\\\mathbb {Z} /m&\cong \mathbb {Z} /p_{m_{1}}^{b_{1}}\times \cdots \times \mathbb {Z} /p_{m_{j}}^{b_{j}}\end{aligned}}}$

どこ${\displaystyle \{p_{m_{1}},\ldots ,p_{m_{j}}\}\subseteq \{p_{n_{1}},\ldots ,p_{n_{i}}\}}$さらに、任意の誘導写像に対して

${\displaystyle \mathbb {Z} /p_{n_{k}}^{a_{k}}\to \mathbb {Z} /p_{m_{l}}^{b_{l}}}$

元の全射から、${\displaystyle a_{k}\geq b_{l}}$そして${\displaystyle p_{n_{k}}=p_{m_{l}},}$2 つの素数に対して${\displaystyle p,q}$唯一の非ゼロ全射

${\displaystyle \mathbb {Z} /p^{a}\to \mathbb {Z} /q^{b}}$

定義できる場合${\displaystyle p=q}$そして${\displaystyle a\geq b}$。

これらの観察結果は、プロ有限整数環を構築する上で極めて重要であり、プロ有限整数環は、そのようなすべての写像の逆極限として与えられる。

デデキントの指標の線形独立性に関する定理。Mをモノイド、k を積分領域とし、 k上の乗法を考慮することでモノイドとみなす。このとき、異なるモノイド準同型f _i : M → kの任意の有限族( f _i ) _{i ∈ I}は線形独立である。言い換えれば、次の条件を満たす要素α _i ∈ kの任意の族( α _i ) _{i ∈ I}は線形独立である。    

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

はファミリー(0) _{i ∈ I}と等しくなければならない。

証明。まず、kが体であると仮定します。そうでない場合は、整域k をその商体で置き換えても何も変わりません。モノイド準同型f _i : M → kをk代数準同型F _i : k [ M ] → kに線形拡張できます。ここで、k [ M ]はk上のMのモノイド環です。すると、線形性により、条件が成り立ちます。   

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0,}$

収量

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

次に、i , j ∈ I ; i ≠ jの場合、2 つのk線形写像F _i  : k [ M ] → kとF _j  : k [ M ] → kは互いに比例しません。そうでなければ、f _iとf _jも比例し、モノイド準同型としてf _i (1) = 1 = f _j (1)を満たすため、等しくなりますが、これは両者が異なるという仮定に矛盾します。      

したがって、核Ker F _iとKer F _jは異なる。k [ M ]/Ker F _i ≅ F _i ( k [ M ]) = kは体であるため、Ker F _iはIのすべての i に対してk [ M ]の極大イデアルである。これらは異なり極大であるため、 i ≠ jのときはいつでもイデアルKer F _iとKer F _jは互いに素である。中国剰余定理 (一般環の場合) により同型が得られる。

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\phi (x+K)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

どこ

${\displaystyle K=\prod _{i\in I}\mathrm {Ker} F_{i}=\bigcap _{i\in I}\mathrm {Ker} F_{i}.}$

したがって、地図

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\mathrm {Ker} F_{i}\\\Phi (x)&=\left(x+\mathrm {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

は全射である。同型写像k [ M ]/Ker F _i → F _i ( k [ M ]) = kの下で、写像Φ は以下に対応する。

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

今、

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

収量

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

写像ψの像内のすべてのベクトル( u _i ) _{i ∈ I}に対して。ψは全射であるため、これは次のことを意味します。

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

すべてのベクトルに対して

${\displaystyle \left(u_{i}\right)_{i\in I}\in \prod _{i\in I}k.}$

したがって、( α _i ) _{i ∈ I} = (0) _{i ∈ I}となる。証明終了。