文章目录
  1. 1. 模运算
  2. 2. 欧几里得算法
  3. 3. 扩展欧几里得算法
  4. 4. 手算扩展欧几里得算法来得到模逆元
  5. 5. 机算扩展欧几里得算法来得到模逆元
  6. 6. 写在最后

本文的数学证明不够严谨,如有疏漏,请多多指教

模运算

先说一下概念
本质上,如果$a=b+kn$对某些整数成立,那个$a \equiv b(mod\ n)$。如果a为正,b0~n, 那么你可以将b看做a被整除后的余数。有时b叫做an余数。有时a叫做与bn同余。这些都是对同一事物的不同叫法而已。

0~n-1的整数组成的集合构成了模n完全剩余集。这意味着,对于每一个整数a,它的余项是从0~n-1的某个数

an的运算给出了a的余数,余数从0~n-1的某个整数,这种运算称为模变换,例如$$5mod3=2$$

模运算就像普通运算一样,他是可交换的、可结合的、可分配的,可以表示为

$$
(a+b)mod\ n=((a\ mod\ n)+(b\ mod\ n))mod\ n \\
(a-b)mod\ n=((a\ mod\ n)-(b\ mod\ n))mod\ n \\
(a\times\ b)mod\ n=((a\ mod\ n)\times(b\ mod\ n))mod\ n \\
(a\times\ (b+c))mod\ n=(((a\times\ b)mod\ n)+((a\times\ c)mod \ n)))mod\ n
$$

这些式子的证明都很简单,都可以把a, b替换成$kn+t(k为整数,t=a\ mod\ b)$的形式, 让然后带入式子即可证明

利用这种性质,我们可以来简化模的运算, 即将a表示为2的幂次方之和

\begin{aligned}
a^{25}mod\ n & = ((((a^2 \times\ a)^2)^2)^2 \times\ a) mod\ n \\
& = (((((((a^2 mod\ n)\times a )mod\ n)^2 mod\ n)^2 mod\ n) mod n)\times\ a)mod\ n \\
\end{aligned}

这种算法叫做加法链C描述如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
unsigned long qe2(unsigned long x, unsigned long y, unsigned long n){
unsigned long s, t, u;
int i;
s=1;
t=x;
u=y;
while (u) {
if (u&1) {
s = (s* t)%n;
}
u>>=1;
t=(t* t)%n;
}
return s;
}

欧几里得算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int gcd(int x, int y){
int g;
if (x < 0) {
x = -x;
}
if(y < 0) {
y = -y;
}
if(x + y == 0){
printf("This is a error");
}
g = y;
while (x>0) {
g = x;
x = y%x;
y=g;
}
return g;
}

代码实在通俗易懂,证明请看维基百科的计算过程和正确性的证明这两章

或者用数学归纳法证明

证明欧几里得算法是正确的,也就是说证明$gcd(ka+b, a) = gcd(a, b)=t(t为最大公约数), 其中k为大于等于1的整数$$

第一步即为$$gcd(t, 0)$$成立

第二步,假设$$gcd(a, b)=t$$成立,那么需证明$$gcd(ka+b, a) = gcd(a, b)$$也成立

$$令a = pt, b= qt(p, t互质), 则ka+b = kpt+qt, 也就是证明\frac{kpt+qt}{pt}=\frac{kp+q}{p}无法再约分$$

使用归谬法, 假设他们都可以约掉s,也就是$$kp+q=vs, p=ws$$那么$$q=vs-kws = s(v-kw)$$ p,q存在共同的因数s,这与p,q互质矛盾

所以第二步也成立

扩展欧几里得算法

扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。已知整数a、b,扩展欧几里得算法可以在求得a、b的最大公约数的同时,能找到整数x、y(其中一个很可能是负数),使它们满足贝祖等式$ax + by = \gcd(a, b)$。

如何证明呢? 你可以翻看算法导论第二版 528 页的证明, 也可以看这篇文章

手算扩展欧几里得算法来得到模逆元

手算的方法在维基, 可以找到

这里求$47x+30y=1$的整数解, 就是求x的值当$47x\ mod\ 30=1$成立的时候

最后x是负的怎么办呢, 请自行看前面模运算的性质吧, 把它变换成正的即可

机算扩展欧几里得算法来得到模逆元

首先, 我表示我真的很想吐槽讲义:Find inverse of 540 mod 1769那张表格就那么出来了!什么证明啊原理啊都没有。

好吧,我来证明一下,为什么这么做是对的

首先我把modulo inverse那里的伪代码用python翻译一遍(python的代码就是那么干净~)

1
2
3
4
5
6
7
8
9
10
11
12
13
f, d = 1769, 540
x1, x2, x3 = 1, 0, f
y1, y2, y3 = 0, 1, d
while y3 != 1:
Q = x3 // y3
t1 = x1 - Q * y1
t2 = x2 - Q * y2
t3 = x3 - Q * y3
x1, x2, x3 = y1, y2, y3
y1, y2, y3 = t1, t2, t3
print(y2+f)

然后是解释,我们把扩展欧几里得算法一步步分解开来
$$
1769x + 540y = 1 \\
(0\times\ y+1\times\ x)\times\ 1769 + (1\times\ y+0\times\ x)540 = 1 \\
(0\times\ y+1\times\ x)\times\ (3\times\ 540+149) + (1\times\ y+0\times\ x)540 = 1 \\
(1\times\ y+3\times\ x)\times\ 540 + (0 + 1\times\ x)\times\ 149 = 1 \\
(1\times\ y+3\times\ x)\times\ (3\times\ 149+93) + (0 + 1\times\ x)\times\ 149 = 1 \\
(3\times\ y+10\times\ x)\times\ 149 + (1\times\ y+3\times\ x)\times\ 93 = 1 \\
(3\times\ y+10\times\ x)\times\ (93+56) + (1\times\ y+3\times\ x)\times\ 93 = 1 \\
(4\times\ y+13\times\ x)\times\ (93+56) + (3\times\ y+10\times\ x)\times\ 56 = 1 \\
$$

对照着那张表格和这里数字的系数, 你一定懂了,这就是算法过程,我们的目的是求x与y

那么为什么最后的y2就是我们要的逆元呢?

这里隐藏着一个信息,即$x1\times\ y2 = y1\times\ x2 + 1$

肉眼看是如此,如何证明?

我们把原来的x1记为x1’, 原来的y1记为y1’,以此类推,根据前面的算法,存在
$$
x1\times\ y2 = y1’\times\ t2 = y1’\times\ (x2’ - Q\times\ y2’) = y1’\times\ x2’ - Qy1’\times\ y2’ \\
x2\times\ y1 = y2’\times\ t1 = y2’\times\ (x1’ - Q\times\ y1’) = y2’\times\ x1’ - Qy2’\times\ y1’
$$

所以说,证明$x1\times\ y2 = y1\times\ x2 + 1$还不是证明$y1’x2’=y2’x1’+1$, 呵呵呵呵,数学归纳法

所以最后把扩展欧几里得算法一步步分解开来得到的式子就是

$$(18\times\ y+59\times\ x)\times\ 1+(29\times\ y+95\times\ x)\times\ 18 = 1$$

根据我们之前得到的$x1\times\ y2 = y1\times\ x2 + 1$,必存在解x=29, y= -95, 你带进去就懂了

写在最后

这篇文章准备加上写作花了我很长的时间,但是由于本人时间有限加上数学功底不够,依然没有办法研究透这几个算法,令人遗憾。还有机算扩展欧几里得算法来得到模逆元的证明方法很是繁琐,如果有更优雅的思考方法,请告诉我,谢谢

文章目录
  1. 1. 模运算
  2. 2. 欧几里得算法
  3. 3. 扩展欧几里得算法
  4. 4. 手算扩展欧几里得算法来得到模逆元
  5. 5. 机算扩展欧几里得算法来得到模逆元
  6. 6. 写在最后