RSA中的数论知识
由于本人的垃圾数学知识,因此只给出怎么用,如何证明就算了
1. gcd 辗转相除法
也被称为欧几里得算法,有两个数a, b我们暂且认为a > b
$$
gcd(a, b) = gcd(b, a % b)
$$
具体远离我也不知道为什么,用就完事儿了
$$
if (b == 0){
return\ a
}
$$
然后就知道了最大公约数,求最小公因数只需要$a * b * gcd(a, b)$就行
python自带math.gcd(a, b)
,不用自己造轮子
2. 贝祖定理
$a \times b \neq 0$就是说a,b 任意一个都不等于0,然后存在$ax+by = gcd(a, b)$
其中x, y不一定都是正数,也可以是负数
3. 扩展欧几里得算法
然后就是通过欧几里得,解出上面的x, y
已知
$$
ax_1 + by_1 = gcd(a, b)\
gcd(a, b) = gcd(b, a % b) = bx_2+a%b\ y_2\
ax_1 + by_1 = bx_2 + (a - a/b\times b)y_2 \
$$
最后一步的a%b 可以变成a - a/b * b,这里的除法/ 指的是整除,5/2=2这种,方便化简
$$
ax_1 + by_1 = bx_2 + ay_2 - b\times a/b\ y_2\
=bx_2 + (a - b \times a / b)y_2
$$
对应相等可得
$$
y1 = x2\
x1 = (a-b\times a/b)y2
$$
x1, y1 依赖于x2, y2 , x2, y2 依赖于 x3, y3,无限递归,最后一个是谁呢,就是gcd(r, 0),这个时候肯定有解,贝祖定理的式子变为了
$$
gcd(r, 0) = rx+0*y
$$
python的代码实现
1 | def extgcd(a, b): |
明显, x=1, y=0,然后回溯回去,就求出了x1, y1
4. 扩展欧几里得求逆元
什么是逆元呢,就是找到$ax=1\ mod\ n$这个x,就称之为x
是a
关于n
的逆元,这个式子变一下
$ax - kn = 1$,而我们假定a, n 互素,因此就有了
$$
ax - kn = gcd(a, n)
$$
然后就是求解上述的extend_gcd了,值得注意的是,由于解出来的k是个负数,我们要个正数,因此只需要进行取模运算就行,python板子
1 | def extgcd(a, b): |
5. 中国剩余定理
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?
求一个数,除3余2,除5余3,除7余2,这个数是多少
写成一个方程组, 要求是$n_i$之间互素
算法:
- 计算
n =n1 * n2 * n3 ...., nk
- 对于第i个方程
- 计算出$m_i = \frac{n}{n_i}$
- 计算出$m_i$对于$n_i$的逆元
invert(m_i, n_i)
- 计算出$c_i=m_i\times m_i^{-1}$(不取模)
- 求出方程的解$x = (\sum a_ic_i)\ mod\ n$
python 板子
1 | def CRT(a: list, n: list): |