矩陣求逆(矩陣求逆計算器在線)

上篇簡單介紹了一下仿射密碼：仿射密碼的加密與解密 ，很多東西都沒有深入去挖掘，這次上完課后對實現它的一些概念公式又有了一個更深的認識。

首先介紹幾個概念：

設矩陣是定義在Zm上的矩陣,

舉個例子：

這其中，9 關于模26 的乘法逆元為3.

模同余：給定一個正整數m，如果兩個整數a和b滿足a-b能夠被m整除，即(a-b)/m得到一個整數，那么就稱整數a與b模m同余，記作a≡b(mod m)。對模m同余是整數的一個等價關系。

例如：

3被2除 余1

5被2除 余1

3，5 被2除有相同的余數

所以 3 同余 5 模 1 ，記做：3 ≡ 5 (mod 1)

其中定義群Zm = {0, 1, 2, ..., m-1}

證明：

必要性：

若a和b除以m留下相同的余數r，

a=q1m+r , b=q2m+r ，q1和q2為某兩個整數

所以a-b=(q1m+r)-(q2m-r)=m(q1-q2)

根據整除定義:(a-b)/m = (q1-q2)，整數相減還是整數，由同余式定義得出結論：a≡b(mod m)

充分性：

假定（其中r1和r1小于m，q1和q2為整數）

a = q1*m+r1 , b = q2*m+r2

則: a-b = (q1-q2)*m + (r1-r2)

因為，則r1-r2=0，即r1=r2

設 a ∈ Zm ,對任意的 b ∈ Zm，同余方程 **ax ≡ b (mod m)** 有唯一解 x ∈ Zm 的充分必要條件是：

gcd(a, m) = 1 (表示a和m的最大公約數等于1)

證明如下：

設a ≥ 1，m ≥ 2, 如果gcd(a, m) = 1,則稱a與m **互素**，Zm中所有與m互素元素的個數用φ(m)來表示（函數φ稱為歐拉函數）

例如φ(10) = 4，因為1,3,7,9均和10互質。

計算方法：

1.先化為標準分解式形式：

example

2.再依照下式規則計算

這其中 {1，5，7，11，13，17，19，23，25，29，31，35} 與36 互質，共計12 個

乘法逆元求解：

1.遍歷，參考上一篇 仿射密碼的加密與解密

2.拓展歐幾里得：