わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

2007年5月21日〜25日

1

Emacsの字,小さいなあ….まあ学生なので目がええんやね.
ところでな,今からいう操作をしてみてくれるか.
Emacsのバッファの中ならどこでもいいので,マウスカーソルを移動して,それで,キーボードのShiftを押しながらね,マウスの左ボタンをクリックするんよ.
あっと,左ボタンは離さんようにね.Shiftキーは,離してくれてええよ.
んで,メニューが出るんやけど,そこをマウスを動かしてやなあ.えっと,『standard: 16-dot medium』を選んで,それでマウスのボタンを離したら…ほらフォントが大きくなった」

2

「とりあえずRSAの鍵生成のあらましを言いましたI gave an outlineが,この中で,計算機で実装するには未定義な処理がいくつか出てきました.順に挙げると,『素数の生成』,『最小公倍数』,『互いに素』の判定,そして『Nを法とする逆数』です.ホワイトボードの隅に書いておきますね*1
これからは,このそれぞれを計算機上で実行できるための数論アルゴリズムを説明していきます.ただし,この順,つまり素数の生成が最初ではありません.
アルゴリズムの書きやすさから,まず最大公約数を説明します.ユークリッドの互除法と呼ばれる,有名なアルゴリズムです.最大公約数が求まれば,互いに素の判定ができます*2.さらに,最小公倍数も簡単に計算できます*3
それから,『Nを法とする逆数』というのは,ユークリッドの互除法の拡張版を用います.それを使えば,1, 2, ...と試すことなく,効率よく逆数が求められるのです.
素数の生成』は,これが決定版!と言えるものはないので,簡単そうなアルゴリズムを一つ,紹介します.ただし,実際のRSAの鍵生成でそのアルゴリズムが使われているとは限らないことは,注意しておきましょう.
このように,『大きな問題』を解決する際に出てくる『小さな問題』の出現順序に沿って,『小さな問題を解決する方法』を挙げていく必要はありません.小さな,未解決の問題をすべて列挙することは,もちろん必要です.解決しやすそうなのから解法を書けばいいのです.そしてすべて解法を書いたら,未解決として挙げた問題をすべてカバーしていることを確認する,それでOKです.コンピュータでプログラムを作る場合だけでなく,レポートや論文を書く場合にも,このやり方が利用できます.」

*1:そして一つ一つクリアすれば,横線を引いて消します.関連する話題は,当日記で「■」を検索すれば,出てきます.

*2:というのも,「aとbは互いに素」は「aとbの最大公約数が1」と等価だからです.

*3:aとbの最大公約数をG,最小公倍数をLと書けば,L=a*b/Gです.