上篇簡單介紹了一下仿射密碼:仿射密碼的加密與解密 ,很多東西都沒有深入去挖掘,這次上完課後對實現它的一些概念公式又有了一個更深的認識。
首先介紹幾個概念:
0. 定義在Zm上的矩陣求逆設矩陣是定義在Zm上的矩陣,
舉個例子:
這其中,9 關于模26 的乘法逆元為3.
1.模同餘模同餘:給定一個正整數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
2.一次同餘方程唯一解定理設 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 個
4.乘法逆元
乘法逆元求解:
1.遍曆,參考上一篇 仿射密碼的加密與解密
2.拓展歐幾裡得:
更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!