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
2
3
4
5
6
7
def extgcd(a, b):
if b == 0:
return 1, 0
else:
x, y= extgcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y

明显, x=1, y=0,然后回溯回去,就求出了x1, y1

4. 扩展欧几里得求逆元

什么是逆元呢,就是找到$ax=1\ mod\ n$这个x,就称之为xa关于n的逆元,这个式子变一下

$ax - kn = 1$,而我们假定a, n 互素,因此就有了
$$
ax - kn = gcd(a, n)
$$
然后就是求解上述的extend_gcd了,值得注意的是,由于解出来的k是个负数,我们要个正数,因此只需要进行取模运算就行,python板子

1
2
3
4
5
6
7
8
9
10
11
12
def extgcd(a, b):
if b == 0:
return 1, 0
else:
x, y= extgcd(b, a % b)
x, y = y, (x - (a // b) * y)
return x, y

def get_inv(a, b):
inv, _ = extgcd(a, b)
inv = (inv % b)
return inv

5. 中国剩余定理

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

求一个数,除3余2,除5余3,除7余2,这个数是多少

写成一个方程组, 要求是$n_i$之间互素

image-20210909010329668

算法:

  • 计算n =n1 * n2 * n3 ...., nk
  • 对于第i个方程
    1. 计算出$m_i = \frac{n}{n_i}$
    2. 计算出$m_i$对于$n_i$的逆元invert(m_i, n_i)
    3. 计算出$c_i=m_i\times m_i^{-1}$(不取模)
  • 求出方程的解$x = (\sum a_ic_i)\ mod\ n$

python 板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def CRT(a: list, n: list):
s = []
n_sum = 1
for i in n:
n_sum *= i
assert len(a) == len(n)
for i in range(len(a)):
m_i = n_sum // n[i]
m_ii = get_inv(m_i, n[i])
s.append(m_ii * m_i)
x = 0
for a_i, c_i in zip(a, s):
x += c_i*a_i
x %= n_sum
return x