フェルマーの小定理からRSA暗号をどうつくるか

作成者:
Bunryu Kamimura
トピック:
整数

p×qを法とする

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)となる。

確かめ