模运算(密码学/数论/算法)

1 什么是模运算

• 模运算的概念
  • 模运算是一种算术运算，常写作a mod n，表示整数a除以正整数n后的余数。
    模数是模运算中的除数n，它决定了结果的范围。
• 公式表达：
  • 对于任意整数a和正整数n，可以将a表示为：a = qn + r，其中0 ≤ r < n，q是整数商，即q = ⌊a/n⌋。
    a除以n的余数是a mod n。
• 示例：
  • 11 mod 7 = 4（11除以7的余数是4）
  • -11 mod 7 = 3（-11除以7的余数是3)

2 模运算性质

2.1 同余关系：

• 当两个整数a和b除以同一个正整数n得到相同的余数时，称a和b模n同余。
  表达式为a ≡ b (mod n)。
• 同余具有传递性 a ≡ b (mod n) and b ≡ c (mod n) 则 a ≡ c (mod n)

2.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 * b) mod n = [(a mod n) * (b mod n)] mod n

2.3 模除运算（逆运算）

模除运算不同于模的加减乘运算，它有自己的意义。

2.3.1 逆元，关于逆元的由来见:逆元

如果有如下公式成立
$$(a^{{}^{\prime }}\ast a)mod(n)=1$$
则称 a’ 为 a 在模n下的一个逆元。

2.3.2 逆元的作用

逆元在模除的场景下需要使用到，比如在如下取模运算中
$$((\frac{a}{v}mod(n))\ast v)mod(n)$$
如下面例子所示：
$$((\frac{103}{3}mod(5))\ast 3)mod(5)=3$$
我们希望通过计算机运算的结果为整数3，由于计算机计算精度有限，就会导致实际运算的结果可能为2.999… ，特别是存在多次模除的时候，就会导致实际进行严重下降，计算机处理过程如下：
$$\begin{array}{rl}& (((\frac{103}{3}mod(5))\ast 3)mod(3)\\ & =(((\mathrm{34.333.........})mod(5))\ast 3)mod(5)\\ & =(\mathrm{4.333......}\ast 3)mod(5)\\ & =\mathrm{12.999....}mod(5)\\ & =\mathrm{2.999...}\end{array}$$
故通过逆元的存在将模除过程中的除法运算改为乘法运算，证明如下：
$$\begin{array}{rl}& (((a\ast v^{{}^{\prime }})mod(n))\ast v)mod(n)\\ & =((((a\ast v^{{}^{\prime }}v)mod(n)))mod(n)\\ & =(a)mod(n)\\ & =((\frac{a}{v}mod(n))\ast v)mod(n)\end{array}$$
故上式中的除法改为乘法之后，如下所示：
$$\begin{array}{rl}& (((103\ast 7)mod(5))\ast 3)mod(3)\\ & =(((721)mod(5))\ast 3)mod(5)\\ & =(1\ast 3)mod(5)\\ & =3mod(5)\\ & =3\end{array}$$
从而避免了计算精度的问题

2.3.3 逆元的求法

逆元有两种求法，一种是通过扩展欧几里得算法求出，一种通过费马小定理求出
不过费马小定理求逆元时要求模的数字必须为质数，即（a）mod n中的n必须为质数
扩展欧几里得算法求逆元时要求a和a必须互质，即（a）mod n中的a与n必须互质

• 扩展欧几里得算法求逆元
  • 欧几里得算法，又称辗转相除法，它是用来求两个正整数的最大公约数
    定理：若整数a ≥ b，则a，b的最大公约数 gcd(a, b) = gcd(b, a mod b)
    
  • 裴蜀定理，裴蜀定理是基于欧几里得算法证明而来
    定理：对于任意整数a、b，设它们的最大公约数为d，则存在整数x、y使得ax + by = d成立‌。特别地，当a与b互质时（即d=1），方程ax + by =1必有整数解
  • 扩展欧几里得算法
    已知 a及
    $$(a^{{}^{\prime }}\ast a)mod(n)=1$$
    求a的逆元 a‘ 的值？
    我们对上式进行转化
    $$(a^{{}^{\prime }}\ast a)mod(n)=a^{{}^{\prime }}\ast a-k\ast n=1$$
    其中，k为一个整数，这里的a’ ，-k 可以理解为裴蜀定理中x，与y，其中a与b都是已知。
    上式也就转化为求方程ax + by =1中x与y的一个解的问题了，关于x与y的求解过程需要用到欧几里得理论
    通过不断的辗转相除法可以得到最后的
    $$\begin{array}{r}{x}^n，y^n\end{array}$$
    推导过程如下：
    
    通过每次的辗转相除法可以得到如下公式:
    

既然我们可以得到最后的
$$\begin{array}{r}{x}^n，y^n\end{array}$$
然后再通过

公式不断的回溯就可以得到最初的x,y的值了，那么这里的x就是 a 在模b下的一个逆元

def gcd(a, b):
    return gcd(b, a % b) if b != 0 else a

# 求ax + by = 1中的一个解
def exGcd(a, b):
    if b == 0:
        return a, 0
    else:
        x1, y1 = exGcd(b, a % b)
        return y1, x1 - a // b * y1

# 返回一个最小的正整数逆元
def moInverse(a, n):
    x, _ = exGcd(a, n)
    return x % n

if __name__ == '__main__':
    print(moInverse(2, 3))
    print(moInverse(7, 3))

• 费马小定理求逆元
  定理：当p为质数且a 不为p的倍数时
  $$\begin{array}{r}{a}^{p-1}mod(p)=1\end{array}$$
  通过上面的恒等式可知
  $$\begin{array}{r}{a}^{{}^{\prime }}=a^{p-2}mod(p)\end{array}$$

• 通过逆元的一个解，可以推导它的无穷个解
  假设a’ 为 a 在模n下的最小正整数解，则它的无穷个解为
  {0<x | x = a’ + k * n}其中k = {0, 1, 2, 3, 4, 5}