質問: 中国人剰余定理自体は理解していて、つまり、以下という認識です。 互いに素な数`a`, `b` があったとき、ある数`x`が * `x ≡ n_a mod a` * `x ≡ n_b mod b` を満たすとき、 ``` x ≡ n mod (a * b) ``` が一意に存在する、ということです。この定理をどのように適用すると、この高速化が確かに正しい計算結果を得ていることになるのかが、分かっていないことです。
回答: 1. `C^d ≡ m1 mod p` かつ `C^d ≡ m2 mod q` ======================================= まず、 `C^d ≡ m1 mod p` かつ `C^d ≡ m2 mod q`を示す。同様の証明となるため、`p` についてのみ示す。 1.1 `C` が `p` の倍数の場合 `C`が`p`の倍数であれば、`C^dP`も`p`の倍数であるから、 `m1 := C^dP ≡ 0 ≡ C^d mod p` 1.2 `C` が `p` の倍数ではない場合 `p` は素数なので、`C` と `p` は互いに素。 フェルマーの小定理により、 `C^(p-1)≡1 mod p`。 また定義より、ある数`k`が存在して、`d = k*(p-1) + dP`。 `mod p` の下、 `C^d = C^(k*(p-1) + dP) = (C^(p-1))^k * C^dP ≡ 1^k * C^dP = C^dP` よって、 `C^d ≡ m1 mod p` 2. 中国人剰余定理の適用 ============= `p != q` であれば、中国人剰余定理の、具体的な計算をすればよくなる。この場合、その実、 `h` や `M'` の計算は、 1. で表された前提に対して、中国人剰余定理を素直に適用しているに過ぎない。結果として計算される `M'` は、`p*q` を法として `C^d` と合同になる。 以下、証明を付けておくと、 今、 `C^d ≡ m2 mod q` より、ある`k`が存在して、`C^d = k*q + m2`. これを `p` の方の合同式に代入して、 `k*q + m2 ≡ m1 mod p` `p` は素数であり、素数体上の演算が可能なので、これについて解いて、 `k ≡ (m1 - m2)*q_inv mod p = h` であって、よって、ある`X` が存在して、 `k = X*p + h`。 k の定義代入しなおして、 `C^d = (X*p + h)*q + m2 ≡ h*q + m2 mod p*q` 以上より示された。 (`p` = `q` は、多分セキュリティ上の理由で、`p`, `q` 生成の段階ではじくべきだと考えられる。)