エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
フェルマーの小定理からRSA暗号をどうつくるか
mp-1≡1 (mod p) ⇒ mp-1-1は pで割り切れる mq-1≡1 (mod q) ⇒ mq-1-1は qで割り切れる では、mod (... 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)となる。