密码学数论简单介绍

文章目录

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

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

模运算

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

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

a模n的运算给出了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描述如下

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;
}

欧几里得算法

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的代码就是那么干净～）

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, 你带进去就懂了

写在最后

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