RSAについて

# 概要 RSA の復号がうまくいくことを述べておく。(よく忘れるので。) 以下とほぼ同様(なので個人メモのようなもの) https://ww1.fukuoka-edu.ac.jp/~sakamott/RSAtop.html ## 補題 1 p, q を相異なる素数とし，x, a, b を整数とする。 このとき、 a ≡ b (mod p) かつ a ≡ b (mod q) ならば　 a ≡ b (mod pq)　が成り立つ。 ### (証明) (a - b)　は p の倍数かつ q の倍数。 p,q は素数なので (a - b ) は pq の倍数。 ## 補題 2( フェルマーの小定理 ) p を素数とし、a を p と互いに素な整数とするとき、 $a^p$ ≡ a ( mod p ) が成り立つ。 ### (証明) a = 0 の時は自明 #### $ a \neq 0 $ の時 $ a^p - a = (1+m)^p - (1+m) = m^p -m + pC_1m^{(p-1)} + pC_2m^{(p-2)} + ... $ となっており、 $ pC_im^{(p-i)} $ は p が素数なので p の倍数となる。 よって $ a^p - a = m^p - m $ mod p となる。 よって帰納法により ok 。 ## RSA暗号のための命題 相異なる素数 p, q に対して L　を p-1 と q-1 の最小公倍数とする。 k ≡ 1 ( mod L ) をみたす整数 k が与えられたとき， 任意の整数 x に対して $x^k$ ≡ x ( mod pq ) が成り立つ。 ## 証明 まず最初に $x^k$ ≡ x ( mod p ) を示す。 ### x が p と素な場合 L は (p-1) の倍数なので $ x^k $ = $ x^{t(p-1)+1} $ と書ける。 フェルマーの小定理より $ x^{(p-1)} $ = 1 mod p より $ x^k $ = $ x^{t(p-1)+1} $ = x mod p . ### x が p と素でない場合 $ x^p $ = 0 mod p より自明 同様に q に対しても $x^k$ ≡ x ( mod q )　が成り立つ。 よって補題1 より $x^k$ ≡ x ( mod pq ) が成り立つ。