Chinese Remainder Theorem
中国剰余定理とは、法が互いに素であるとき、連立合同式がそれらの積を法としてただ一つの解を持つという定理である。
目的
大きな法による演算を並列可能な小さな法の演算へ分解し、多倍長整数の合同演算を高速化する。
メカニズム
x ≡ a_i (mod n_i)（n_i は互いに素）のとき、x は mod N（N=∏n_i）でただ一つの解を持つ。N_i=N/n_i、M_i=N_i^(-1) mod n_i とおくと、x=∑a_i*N_i*M_i mod N で解が得られる。
ユースケース
- RSA の高速化
- 多倍長整数のモジュラ演算
- 数論的アルゴリズム