SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

Tips RSA, 合同式の逆元を求める.

僕は暗号化あたりのアルゴリズムが好きなんだけれど、RSA合同式の逆元の求め方ってなんだっけ?と年始早々ど忘れしたので改めて勉強し直そうと思う。
合同式(モジュラー算術、時計算術とも言う)とは以下の定義のものを指す。

二つの整数aとbにおいて、その差(a - b)が整数nで割り切れるとき、aはnを法としてbと合同である。


基本情報あたりで見たっぽい知識だが、この逆元を求めるには拡張ユークリッドの互除法を使う。
以下逆元を求めるPythonコードになる。


次にこのegcdを使って合同式の逆元を求める。


modinvで式中のxを求められた。上記はWikipediaModular multiplicative inverseが一番理解しやすかったので、中の疑似コードを参照した。いざまとめると全然簡単だけれど、ポンッとド忘れちゃうのでアルゴリズムの知識をどんどん鍛えていきたい。

年始はひたすらScikit-Learnの写経と会社の先輩からの課題図書を読んでいるが、OSSのコードリーディングをするとまだまだ知らない書き方が出てきてテンションが非常に上がる。課題図書は数式ばっかりでもう頭がパンク寸前で辛い。数学はホント2016年一番力入れないといけないテーマだ。