RSA中的数论知识

由于本人的垃圾数学知识，因此只给出怎么用，如何证明就算了

1. gcd 辗转相除法

也被称为欧几里得算法，有两个数a, b我们暂且认为a > b
gcd(a,b)=gcd(b,a
具体远离我也不知道为什么，用就完事儿了
if(b==0)returna
然后就知道了最大公约数，求最小公因数只需要a∗b∗gcd(a,b)就行

python自带math.gcd(a, b)，不用自己造轮子

2. 贝祖定理

a×b≠0就是说a,b 任意一个都不等于0，然后存在ax+by=gcd(a,b)

其中x, y不一定都是正数，也可以是负数

3. 扩展欧几里得算法

然后就是通过欧几里得，解出上面的x, y

已知
ax1+by1=gcd(a,b)gcd(a,b)=gcd(b,aax1+by1=bx2+(a−a/b×b)y2
最后一步的a%b 可以变成a - a/b * b，这里的除法/ 指的是整除，5/2=2这种，方便化简
ax1+by1=bx2+ay2−b×a/by2=bx2+(a−b×a/b)y2
对应相等可得
y1=x2x1=(a−b×a/b)y2
x1, y1 依赖于x2, y2 , x2, y2 依赖于 x3, y3，无限递归，最后一个是谁呢，就是gcd(r, 0)，这个时候肯定有解，贝祖定理的式子变为了
gcd(r,0)=rx+0∗y
python的代码实现

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=1modn这个x，就称之为x是a关于n的逆元，这个式子变一下

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

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，这个数是多少

写成一个方程组， 要求是ni之间互素

• 计算n =n1 * n2 * n3 ...., nk
• 对于第i个方程
• 1. 计算出mi=nni
  2. 计算出mi对于ni的逆元invert(m_i, n_i)
  3. 计算出ci=mi×mi−1（不取模）
• 求出方程的解x=(∑aici)modn

python 板子

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