ぺんぎんさんのおうち

日本語勉強中のドイツ産ペンギンがいろんなことを書く

26.10.2017

もうすぐサマータイムも終わり.

今日は情報理論の授業.

内容はRSAの暗号化と複合, Key-Genについて

 

もやもやしてた問題が解決した.

modularの逆数, 

mを法とする場合のaの逆元a^-1を求める場合方法が2つあって

1. 拡張ユークリッド

2. オイラーの定理フェルマーの小定理

である.

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日