2014年8月8日金曜日

数学のあつまり

で,大学へ.



はじめは,RSA暗号の話.

新教育課程に,不定方程式とかユークリッドの互除法が入ってきたので,昔,情報の授業でRSAを扱ったときに,若干はしょったところを丁寧にできる感じがした.>以前のの記事(RSA)以前の記事(不定方程式)

つまり,暗号化と復号に用いる「累乗」の数 d,e を求めるときに,本来ならば拡張ユークリッドの互除法を用いるのだが,授業では面倒なので,こちらで一覧表を作って見せて,その中からうまくいくものを探させたのだ.
授業でやった p=3,q=11 くらいなら一覧表を見て探せるわけだが,実際の RSA 暗号ではp も q も300桁を超える素数だから,見て探すようなものでは当然ない.
平文 M に対し,暗号文 C=M^e mod pq.復号は M=C^d mod pq.
ここで,p,q は巨大素数.
累乗の d,e は,暗号化の e (公開鍵)は素数を適当にえらぶ.11 とか 257 とか 65537 とか.(L と素であればいいけど,素数なら間違いない)
そして,e から d(秘密鍵)を探すのは,偶数 (p-1) と (q-1) の最小公倍数 L に対して,de=nL+1 ⇔ de+(-n)L=1 mod pq となる,d,n を探す.
そして,pq,と e を公開し,d,n を秘密にする.
そこで,ユークリッドの互除法で,効率よく見つけるわけだ.ユークリッドの互除法は,約分のネタで何度もやっているが.>以前の記事
具体的には,最小公倍数 L を見つけるために,ユークリッドの互除法で p-1,q-1 の最大公約数を見つける.すると,最小公倍数は (p-1)(q-1)÷最大公約数 となる.
さらに,dから e,n を探すのも拡張ユークリッドの互除法を用いる.

ユークリッドの互除法は人類最古の「アルゴリズム(手順)」であるから,コンピュータを使えば数千桁の整数でも一瞬で計算できる.(電卓を手で打つならpq が8桁程度で数分,紙と鉛筆なら pq が3桁程度で数分.)

新教育課程のユークリッドの互除法は,なにか唐突な感じの扱いになっているけれど,「こんなふうに役立っている」と,うまく教材に盛り込めるかもしれぬ.
まぁどちらにしても,理論を扱うよりは,手を動かしたほうが楽しいだろう.

その後,施設見学.
前も来たことあるな.

ホログラム.

見る角度を変えると・・・
なんか,皆さんエグザイルになってますよw

午後も,講義2本.最適化問題と,高大連携.

その後,図書館の見学.
床の丸いのから,空調の空気が出ている.

その上に立つと涼しい.
スカートだとマリリンモンローみたいに・・・そんな強くないです.
すいません,いつものように下駄.
図書館なので静かに歩いていたら足がつりそうになったw

丸いのは動きません.ベンチの背もたれです.

0 件のコメント:

コメントを投稿

「コメントの記入者:」は「匿名」ではなく,「名前/URL」を選んで,なにかニックネームを入れてください.URL は空欄で構いません.