中国剰余定理を使う
中国剰余定理(CRT)は、連立合同式を解きます。アルゴリズムと、RSA の高速化や秘密分散への応用を学びましょう。
- 1
中国剰余定理(CRT)は次を述べます。法 m1、m2、…、mn が対ごとに互いに素なら、連立合同式 x ≡ a1 (mod m1)、x ≡ a2 (mod m2)、…、x ≡ an (mod mn) は M = m1 * m2 * … * mn を法として一意な解を持ちます。CRT は RSA の復号(p と q を別々に使い、CRT で合成。4 倍高速)や Shamir の秘密分散で使われます。
- 2 中国剰余定理計算ツール →
連立合同式を解きます。剰余 [a1, a2, …] と法 [m1, m2, …] を入力してください。ツールは解 x と合成法 M を計算します。検証:x mod m1 = a1、x mod m2 = a2 など。
- 3 最大公約数計算ツール →
法が対ごとに互いに素かを確認します(すべての i ≠ j で gcd(mi, mj) = 1)。どれかの組が共通因数を持つと、CRT は直接適用できません。連立方程式は解を持たないか、複数の解を持つ可能性があります。
よくある質問
- CRT はどう RSA を高速化しますか?
- RSA 復号は m = c^d mod n(n = p*q)を計算します。CRT を使うと、m_p = c^(d mod p-1) mod p と m_q = c^(d mod q-1) mod q を別々に計算し(より小さな指数と法)、CRT で合成します。2 つのべき乗計算が半分のサイズの数を使い、並列化もできるため、4 倍高速です。
- 法が互いに素でない場合はどうなりますか?
- CRT は法が対ごとに互いに素であることを要求します。そうでない場合、連立方程式は解を持たない(合同式が矛盾する場合)か、複数の解を持ちます。まず対ごとの GCD を確認してください。互いに素でない法には、一般化 CRT を使うか、代入手法で解いてください。