もうすぐサマータイムも終わり.
今日は情報理論の授業.
内容はRSAの暗号化と複合, Key-Genについて
もやもやしてた問題が解決した.
modularの逆数,
mを法とする場合のaの逆元a^-1を求める場合方法が2つあって
1. 拡張ユークリッド
である.
1, 2共にGCD(a, m) = 1 である必要がある.
(打つのが面倒だったので合同の記号を使っていない)
拡張ユークリッドで逆元を求める方法について,
aの逆元a^-1は, a*x = 1 (mod m) となる x を求めることで解決する.
ここで式の見方を少し変えると
1 + q*m = a*x (q は任意の自然数) となる.
これを整理する
a*x - q*m = 1
になった(mod m は略してある) どこかでみたことある.
そう, これはベズーの等式 : ax + by = GCD(a. b) だ
qはどうでもいいので, 上の式を満たす解(x, q) の x が a の逆元となる.
留学満了まで111日
