文章目录

• 0.定义在Zm上的矩阵求逆
• 1.模同余
• 2.一阶同余方程的唯一解定理
• 3.欧拉函数和欧拉定理
• 4.乘法逆元素

第一部分简要介绍仿射密码:仿射密码的加密和解密。很多东西没有深入探究。上完这堂课，我对一些概念公式有了更深的理解来实现它。

首先，介绍一些概念:

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(模1)

其中组Zm = {0，1，2，…，m-1}

证明:

必要性:

如果a和b除以m得到相同的余数r，

A = q1mrr，b = q2mrr，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)

证明如下:

3.欧拉函数和欧拉定理

设a ≥ 1，m ≥ 2，若gcd(a，m) = 1，则A和m **称为互质**，Zm中所有含M的互质元素的个数用φ(m)表示(函数φ称为欧拉函数)

比如φ(10) = 4，因为1，3，7，9都是10的素数。

计算方法:

1.第一个转化为标准分解形式:

例子

2.根据以下公式计算

其中{1，5，7，11，13，17，19，23，25，29，31，35}和36是素数，总共是12。

4.乘法逆元素

乘法逆解:

1.遍历，参考上一篇文章仿射密码的加密解密。

2.展开欧几里德: