数学のあつまり

で，大学へ．

はじめは，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桁程度で数分．）

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

その後，施設見学．

前も来たことあるな．

ホログラム．

見る角度を変えると・・・

なんか，皆さんエグザイルになってますよｗ

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

その後，図書館の見学．

床の丸いのから，空調の空気が出ている．

その上に立つと涼しい．

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

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