密码学数论简单介绍
本文的数学证明不够严谨,如有疏漏,请多多指教
模运算
先说一下概念
本质上,如果$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
描述如下
|
|
欧几里得算法
|
|
代码实在通俗易懂,证明请看维基百科的计算过程和正确性的证明这两章
或者用数学归纳法证明
证明欧几里得算法是正确的,也就是说证明$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的代码就是那么干净~)
|
|
然后是解释,我们把扩展欧几里得算法一步步分解开来
$$
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, 你带进去就懂了
写在最后
这篇文章准备加上写作花了我很长的时间,但是由于本人时间有限加上数学功底不够,依然没有办法研究透这几个算法,令人遗憾。还有机算扩展欧几里得算法来得到模逆元的证明方法很是繁琐,如果有更优雅的思考方法,请告诉我,谢谢