RSA復号の正当性

ここで $ed \equiv 1 \pmod{\phi(n)}$ により、モジュラー合同の定義から、ある非負整数 $k$ が存在して $ed = 1 + k\phi(n)$ が成り立つ。

場合1:$\gcd(m,n)=1$ のとき。オイラーの定理より $m^{\phi(n)} \equiv 1 \pmod n$ が成り立つので、両辺を $k$ 乗して $m$ を掛けると $m^{ed} = m \cdot (m^{\phi(n)})^{k} \equiv m \cdot 1^{k} \equiv m \pmod n$ が得られる。

場合2:$\gcd(m,n) \ne 1$ のとき。$n = pq$ であるから、これは $p$ が $m$ を割り切るか、または $q$ が $m$ を割り切ることを意味する($m$ は $n$ より小さいので両方が同時に成り立つことはない)。法 $p$ のもとで考える:もし $p$ が $m$ を割り切るなら、$m$ と $m^{ed}$ はともに法 $p$ のもとで $0$ と合同である。そうでなければ $\gcd(m,p)=1$ であり、フェルマーの小定理より $m^{p-1} \equiv 1 \pmod p$ が成り立ち、$(p-1)$ が $\phi(n)$ を割り切ることから、場合1と同じ計算で $m^{ed} \equiv m \pmod p$ が示される。法 $q$ についても同様の議論により $m^{ed} \equiv m \pmod q$ が示される。

中国剰余定理により、法 $p$ と法 $q$ のそれぞれで成り立つ合同式は、その積 $n=pq$ を法としても成り立つ。したがって $(m^e)^d \equiv m \pmod n$ はすべてのメッセージ $m$ に対して成り立ち、$n$ と互いに素なものだけに限らない。