密码学数学基础（一）整除

一、整除

1.1 自然数与整数

在数论中，自然数也叫作正整数，即\(1,2,3\cdots,n,n+1,\cdots\)。整数指正整数、负整数和零。记\(\mathbb{Z}\)表示全体整数的集合，\(\mathbb{N}\)表示全体自然数的集合。

定理1.1（最小自然数原理）：设\(T\)是\(\mathbb N\)的一个非空子集，则必有\(t_0\in T\)，使得对任意的\(t\in T\)，有\(t_0\le t\)，即\(t_0\)是\(T\)中的最小自然数。

定理1.2（最大自然数原理）：设\(M\)是\(\mathbb N\)的一个非空子集，若\(M\)有上界，则必有\(m_0\in M\)，使得对任意的\(m\in M\)，有\(m\le m_0\)，即\(m_0\)是\(M\)中的最大自然数。

1.2 整除与素数

定义1.1：设\(a,b\in\mathbb{Z}\)，如果存在\(q\in\mathbb{Z}\)，使得\(b=aq\)，那么就说\(a\)整除\(b\)，或\(b\)被\(a\)整除，记作\(a\mid b\)，称\(b\)是\(a\)的倍数，\(a\)是\(b\)的因子；否则就说\(a\)不整除\(b\)，或\(b\)不能被\(a\)整除，记作\(a\nmid b\)。

对于非零整数\(b\)，显然\(\pm1,\pm b\)是\(b\)的因子，我们称其为显然因子，其他因子称为非显然因子或真因子。

定义1.2：设整数\(p\ne0,\pm1\)，如果\(p\)除了显然因子\(\pm1,\pm p\)外没有其他的因子，那么\(p\)就称为素数。若整数\(a\ne0,\pm1\)，且\(a\)除显然因子外还有真因子，则称\(a\)为合数。

一般情况下，我们只考虑正的素数。

定理1.3：若\(a\)为合数，则\(a\)的最小真因子为素数。

证明：若\(a\)的最小真因子\(d\)不为素数，则\(d\)必有真因子\(d'\)，显然\(d'\)也是\(a\)的因子，因此\(a\)存在更小的因子\(d'\)，与假设不符。

定理1.4：素数有无穷多个。

证明：假设只有有限个素数，设为\(p_1,p_2,\cdots,p_k\)，考虑\(a=p_1p_2\cdots p_k+1\)，由定理1.3知，\(a\)的最小真因子一定为素数，记为\(p\)。既然\(p\)是素数，那么它就一定等于某个\(p_i\)，所以\(p\mid a\)且\(p\mid p_1p_2\cdots p_k\)，从而\(p\mid 1\)，这与\(p\)是素数矛盾。

定理1.5（带余除法）：设\(a,b\)是两个给定的整数且\(a\ne0\)，那么一定存在唯一的一对整数\(q\)和\(r\)，满足 \[ b=qa+r,0\le r<|a| \] 其中\(r\)称为余数，\(a\mid b\)的充要条件是\(r=0\)。

1.3 最大公约数与最小公倍数

定义1.3：设\(a_1,a_2\)是两个整数，如果\(d\mid a_1\)且\(d\mid a_2\)，那么就称\(d\)是\(a_1\)和\(a_2\)的公约数（公因子）；最大的那个\(d\)称为最大公约束（最大公因子），记作\((a_1,a_2)\)或\(gcd(a_1,a_2)\)。

定义1.4：设\(a_1,a_2\)是两个整数，若\((a_1,a_2)=1\)，则称\(a_1\)和\(a_2\)是互素的（或既约的）。

定义1.5：设\(a_1,a_2\)是两个均不等于零的整数，如果\(a_1\mid l,a_2\mid l\)，则称\(l\)是\(a_1\)和\(a_2\)的公倍数；最小的那个\(l\)称为最小公倍数，记作\([a_1,a_2]\)。

1.4 欧几里得算法

也称辗转相除法，主要用于求解最大公约数。

定理1.6（欧几里得算法）：设\(a,b\)是两个给定的整数，\(b\ne0\)且\(b\)不整除\(a\)，重复应用带余除法可得下面等式： \[ \begin{align} a&=q_0b+r_0&&(1)\\ b&=q_1r_0+r_1&&(2)\\ r_0&=q_2r_1+r_2&&(3)\\ &\cdots\cdots\\ r_{k-3}&=q_{k-1}r_{k-2}+r_{k-1}&&(k)\\ r_{k-2}&=q_kr_{k-1}+r_{k}&&(k+1)\\ r_{k-1}&=q_{k+1}r_k&&(k+2) \end{align} \]

证明：根据带余除法的性质，有\(|b|>r_0>r_1>\cdots>r_k>0\)，因此只有有限个\(r\)，上述等式的个数是有限的。不断迭代等式，最坏的情况下\(r_k=1\)，此时等式\((k+2)\)必然成立，因此一定存在这样的\(r_k\)，使得\(r_k\mid r_{k-1}\)。

下面的定理非常重要，尤其是第二点，它是很多算法的基础。

定理1.7：在定理1.6的条件和符号下，有

• \(r_k=gcd(a,b)\)；
• （裴蜀定理）存在整数\(x,y\)，使得\(gcd(a,b)=ax+by\)。

证明：

• 根据上述等式，\(gcd(a,b)=gcd(b,r_0)=gcd(r_0,r_1)=\cdots=gcd(r_{k-1},r_k)\)，而\(r_k\mid r_{k_1}\)，因此\(r_k\)就是最大公约数。
• 由等式\((k+1)\)，\(r_k\)可以表示为\(r_{k-1}\)和\(r_{k-2}\)的线性组合，利用等式\((k)\)消去\(r_{k-1}\)，则\(r_k\)又可以表示为\(r_{k-2}\)和\(r_{k-3}\)的线性组合，不断这样带入上一个式子，直到将\(r_k\)表示为\(a\)和\(b\)的线性组合。

举个计算的例子方便理解。

例1.1：求75和48的最大公约数，并将其表示成线性组合的形式。

解： \[ \begin{align} 75&=1\times48+27\\ 48&=1\times27+21\\ 27&=1\times21+6\\ 21&=3\times6+3\\ 6&=2\times3 \end{align} \] 因此最大公约数为3。上述逆过程如下： \[ \begin{align} 3&=21-3\times6\\ 3&=21-3\times(27-1\times21)=-3\times27+4\times21\\ 3&=-3\times27+4\times(48-1\times27)=4\times48-7\times27\\ 3&=4\times48-7\times(75-1\times48)=-7\times75+11\times48 \end{align} \] 验算一下确实成立，得到：\(3=-7\times75+11\times48\)。

结合例子，下面来看算法：

• 欧几里得算法求最大公约数

  # 求a和b的最大公约数
  def gcd(a, b):
      # return b if a % b == 0 else gcd(b, a % b)
      return a if b == 0 else gcd(b, a % b)

  注释的那一行很好理解，当b整除a时直接返回b，否则将b和余数继续带入函数。从逻辑上看a应该需要大于b，但实际上如果a小于b的话代入函数下一轮会交换ab，因此谁大谁小都无所谓。下面一行意思是一样的，当a % b == 0时，再多代入一轮函数，b就会传给a，因此最大公约数应该返回a，而b就等于0了。

• 扩展欧几里得算法

  扩展欧几里得算法即找到这样一组线性组合，使得\(gcd(a,b)=ax+by\)。

  # 求x、y满足：ax + by = gcd(a, b) = d
  def exgcd(a, b):
      if b == 0:
          x = 1
          y = 0
          return a, x, y
      d, x0, y0 = exgcd(b, a % b)
      x = y0
      y = x0 - a // b * y0
      return d, x, y

  递归的核心函数和gcd函数类似，当b==0时，a即为最大公约数，此时令系数x = 1, y = 0，满足ax + by = d。然后就需要一层一层反推系数，结合例1.1，有：

  正推（例）	正推	反推	反推（例）
  \(27=1\times21+6\)	① \(a=q_1b+r_1\)	④
  \(21=3\times6+3\)	② \(a_0=q_2b_0+r_2\) 因为是递归这里还是用ab表示 \(a_0=b,b_0=r_1\)	③ \(d=a_0x_0+b_0y_0\)	\(3=21-3\times6\)

  按顺序正推从①到②，然后上一层递归已经返回了③中的系数，现在要求④的表达式。根据正推的关系将\(a_0=b,b_0=r_1\)带入③得 \[ \begin{align} d&=bx_0+r_1y_0\\ &=bx_0+(a-q_1b)y_0\\ &=ay_0+(x_0-q_1y_0)b \end{align} \] 这里就将上一层的\(a_0,b_0\)代换为这一层的\(a,b\)了，按照\(a\)对应的系数是\(x\)，\(b\)对应的系数是\(y\)，那么新系数就是 \[ \begin{cases} x=y_0\\ y=x_0-q_1y_0=x_0-a//b\cdot y_0 \end{cases} \] 对应了代码中的两行赋值，至此代码就讲完了。

扩展欧几里得算法可以用来求解二元一次不定方程\(ax+by=c\)，先看下面定理。

定理1.8：二元一次不定方程\(ax+by=c\)（\(a,b\)为非零整数）有整数解的充要条件是\(gcd(a,b)\mid c\)。

证明：

• 必要性：若方程有整数解\(x_0,y_0\)，则\(ax_0+by_0=c\)，因为\(gcd(a,b)\mid a,b\)，所以\(gcd(a,b)\mid c\)；
• 充分性：若\(gcd(a,b)\mid c\)，则存在整数\(k\)使得\(c=k\cdot gcd(a,b)\)，由裴蜀定理，存在整数\(s,t\)使得\(as+bt=gcd(a,b)\)，令\(x_0=ks,y_0=kt\)，则有\(ax_0+by_0=k\cdot gcd(a,b)=c\)，方程有解。

求解方程时，只需用exgcd求出系数\(s,t\)，再扩大\(k\)倍就得到方程的特解\(x_0\)和\(y_0\)了，通解为 \[ \begin{cases} x=x_0+\frac{b}{gcd(a,b)}t\\ y=y_0-\frac{a}{gcd(a,b)}t \end{cases} \]

1.5 最大公约数理论

定理1.9（最大公约数理论）

• \(a_j\mid c(1\le j\le k)\)的充要条件是\([a_1,\cdots,a_k]\mid c\)。

• 设\(D\)是正整数，那么\(D=(a_1,\cdots,a_k)\)的充要条件是：

  （1）\(D\mid a_j(1\le j\le k)\)；（2）若\(d\mid a_j(1\le j\le k)\)，则\(d\mid D\)。

• 设\(m>0\)，有\(m(b_1,\cdots,b_k)=(mb_1,\cdots,mb_k)\)。

• \((a_1,\cdots,a_{k+r})=((a_1,\cdots,a_k),(a_{k+1},\cdots,a_{k+r}))\)。

• 设\((m,a)=1\)，则有\((m,ab)=(m,b)\)。

• 设\((m,a)=1\)，那么若\(m\mid ab\)，则\(m\mid b\)。

• \([a_1,a_2](a_1,a_2)=|a_1a_2|\)。

• 设\(a_1,\cdots,a_k\)是不全为零的整数，\(x_j\in\mathbb{Z}(1\le j\le k)\)，有：

  • \((a_1,\cdots,a_k)=\min\{s=a_1x_1+\cdots+a_kx_k,s>0 \}\)；
  • 一定存在这样的系数\(x_j\)使得：\((a_1,\cdots,a_k)=a_1x_1+\cdots+a_kx_k\)。

证明：

前7条仅给出理解，主要证明最后一条。

• 公倍数一定是最小公倍数的倍数。

• 公约数一定是最大公约数的约数。

• 略。

• 求若干个数的最大公约数可以任意分组。

• 求\(m\)与另一个数的最大公约数时，可以把另一个数中与\(m\)互素的因数去掉。

• 若一个数被\(m\)整除，把这个数中与\(m\)互素的因素去掉仍然被\(m\)整除。

• 最大公约数乘以最小公倍数等于这两个数的乘积。

• 设\(S=\{a_1x_1+\cdots+a_kx_k\}\)且\(S>0\)，即\(S\)表示\(a_1,\cdots,a_k\)的线性组合中的所有正整数。由最小自然数原理知\(S\)中必有最小正整数\(s_0\)。对任一公约数\(d\mid a_j\)，必有\(d\mid s_0\)（因为\(s_0\)是\(a_j\)的线性组合），所以\(|d|\le s_0\)。另外，对任一\(a_j\)，由带余除法可知 \[ a_j=q_js_0+r_j,\quad0\le r_j\le s_0 \] 因为\(a_j\)和\(q_js_0\)都属于\(S\)，所以\(r_j\)也属于\(S\)或为\(0\)。若\(r_j>0\)，由于\(r_j\le s_0\)，这与\(s_0\)的最小性矛盾，所以\(r_j=0\)，即\(s_0\mid a_j\)（\(s_0\)是公约数），结合前面的\(|d|\le s_0\)，所以\(s_0\)是最大公约数。

特别地，\((a_1,\cdots,a_k)=1\)的充要条件是存在整数\(x_1,\cdots,x_k\)使得\(a_1x_1+\cdots+a_kx_k=1\)。

1.6 算术基本定理

定理1.10（算术基本引理）：设\(p\)是素数，\(p\mid a_1a_2\)，则\(p\mid a_1\)和\(p\mid a_2\)中至少有一个成立。一般地，若\(p\mid a_1\cdots a_k\)则\(p\mid a_1,\cdots,p\mid a_k\)中至少有一个成立。

证明：

若\(p\nmid a_1\)，则\((p,a_1)=1\)，由定理1.9第6条可得\(p\mid a_2\)。一般的情形只需多次使用该结论。

定理1.11（算术基本定理）：设\(a>1\)，那么必有 \[ a=p_1p_2\cdots p_s \] 其中\(p_j(1\le j\le s)\)是素数，且在不计次序的意义下，该表示唯一。将上述表示中，相同的素数合并，可得 \[ a=p_1^{\alpha_1}\cdots p_s^{\alpha_s},\ p_1<p_2<\cdots<p_s \] 该式称为正整数\(a\)的标准素因数分解式。

证明：

首先，\(a\)一定能表示成素数的乘积。否则，则设不能表示成素数乘积的正整数的集合为\(T\)，设\(t_0\)是\(T\)中最小的正整数。显然\(t_0\)不可能是素数，则它为合数，那么\(t_0=t_1t_2\)，\(t_1\)和\(t_2\)都能被素数的乘积表示，那么\(t_0\)也能被素数的乘积表示，这与\(t_0\)的最小性矛盾。

下证唯一性。不妨设\(p_1\le p_2\le\cdots\le p_s\)，若还有表达式 \[ a=q_1q_2\cdots q_r,\quad q_1\le q_2\le\cdots\le q_r \] 下面来证明必有\(r=s,p_j=q_j\)。不妨设\(r\ge s\)，由算术基本定理可知，\(q_1\mid a=p_1p_2\cdots p_s\)，则必有某个\(p_j\)满足\(q_1\mid p_j\)，因为它们都是素数，所以\(q_1=p_j\)。同理，必有某个\(q_i\)满足\(p_1=q_i\)。由于\(q_1\le q_i=p_1\le p_j=q_1\)，所以\(p_1=q_1\)。这样依次可得\(p_2=q_2,\cdots,p_s=q_s\)，从而\(q_{s+1}\cdots q_r=1\)，所以\(s=r\)，证毕。

定义1.6：设\(x\)是实数，\([x]\)表示不超过\(x\)的最大整数，称为\(x\)的整数部分。记\(\{x\}=x-[x]\)，称为\(x\)的小数部分。

1.7 SageMath

# 是否整除
sage: 3.divides(9)
True
sage: 3.divides(7)
False

# 素数集合
sage: P = Primes()
sage: P
Set of all prime numbers: 2, 3, 5, 7, ...
sage: P.unrank(0)   # 第k个素数
2-
sage: P.unrank(10)
31
sage: P.next(31)    # 大于x的下一个素数
37
sage: prime_pi(100) # 小于等于x的素数个数
25

sage: gcd(75, 48)   # 最大公约数
3
sage: xgcd(75, 48)  # 扩展欧几里得
(3, -7, 11)
sage: lcm(6, 9)     # 最小公倍数
18

# 因式分解
sage: factor(60)
2^2 * 3 * 5