フェルマーの小定理からRSA暗号をどうつくるか
p×ｑを法とする
mp-1≡1 (mod p) ⇒ mp-1-1は pで割り切れる
mq-1≡1 (mod q) ⇒ mq-1-1は qで割り切れる
では、mod (p·q)にするにはどうしたら良いか？
つまりpでもqでも割り切れる数は？
m(p-1)(q-1)-1を考えてみると、
(m(p-1))(q-1)-1は qで割り切れる。
(m(q-1))(p-1)-1は pで割り切れる。
よってm(p-1)(q-1)-1は p·qで割り切れる。（p·q=nとおく）⇒ m(p-1)(q-1)≡1 (mod n)
ここで、（ ）≡m にするために、両辺にmをかける。
m(p-1)(q-1)·m≡m (mod n)
m(p-1)(q-1)+1≡m (mod n)
この時、(p-1)(q-1)+1＝e·dとすると、(me)d≡m (mod n)となる。