Mengzelev's Blog

算法导论学习笔记-数论算法

Word count: 2,474 / Reading time: 11 min
2019/04/06 Share

输入规模和算数计算的代价

给定$k$个整数输入$a_1,a_2,\cdots ,a_k$,如果算法可以在关于$\lg~a_1,\lg~a_2,\cdots ,\lg~a_k$的多项式时间内完成,即算法在关于二进制编码后的输入长度的多项式时间内完成,则称该算法为多项式时间算法

当输入很大时,基本运算也会变得耗时。
两个$\beta$位整数相乘需要耗时$\Theta(\beta^2)$.
一个$\beta$为整数除以另一个较短整数的商或余数需要耗时$\Theta(\beta^2)$

基础数论概念

整除性与约数

你懂的

素数与合数

你也懂的

除法定理、余数和等模

定理31.1(除法定理): 对于任何整数$a$和任何正整数$n$,存在唯一整数$q$和$r$,满足$0\le r<n$且$a=qn+r$

根据整数模$n$的余数,可以将所有整数划分成$n$个等价类。
包含整数$a$的模$n$等价类为$\left[a\right]_n={a+kn:k\in\mathbb{Z}}$
所有这类等价类的集合是$\mathbb{Z}_n={[a]_n:0\le a\le n-1}$

公约数与最大公约数

公约数的重要性质:

  • $d\mid a$且$d\mid b$蕴含$d\mid (a+b)$且$d\mid (a-b)$
  • 对任意整数$x$和$y$,都有$d\mid a$且$d\mid b$蕴含$d\mid(ax+by)$
  • $a\mid b$且$b\mid a$蕴含$a=\pm b$

定理31.2: 如果任意整数$a$和$b$不都为0,则gcd$(a,b)$是$a$与$b$线性组合集${ax+by:x,y\in\mathbb{Z}}$中的最小正元素。(最小正线性组合)

推论31.3: 对任意整数$a$与$b$,如果$d\mid a$且$d\min b$,则$d\mid gcd(a,b)$

推论31.4: 对所有整数$a$和$b$以及任意非负整数$n$,有$gcd(an,bn)=n~gcd(a,b)$

推论31.5: 对于任意正整数$n,a$和$b$,如果$n\mid ab$且$gcd(a,n)=1$,则$n\mid b$.

互质数

定理31.6: 对任意整数$a,b$与$p$,如果$gcd(a,p)=1$且$gcd(b,p)=1$,则$gcd(ab,p)=1$.

唯一因子分解定理

定理31.7: 对所有素数$p$和所有整数$a,b$,如果$p\mid ab$,则$p\mid a$或$p\mid b$(或两者都成立)。

定理31.8(唯一因子分解定理): 合数$a$仅能以一种方式写成如下乘积形式
$$a=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$$
其中$p_i$为素数,$p_1<p_2<\cdots p_r$且$e_i$为正整数

最大公约数

定理31.9(GCD递归定理): 对任意非负整数$a$和任意正整数$b$,$gcd(a,b)=gcd(b,a\bmod b)$

欧几里得算法

运行时间

引理31.10: 如果$a>b\ge 1$并且EUCLID($a,b$)执行了$k\ge 1$次递归调用,则$a\ge F_{k+2}, b\ge F_{k+1}$.($F_n$为斐波那契数列的第$n$项)

定理31.11(Lame定理): 对任意整数$k\ge 1$,如果$a>b\ge 1$,且$b<F_{k+1}$,则EUCLID($a,b$)的递归调用次数少于$k$次
该上界是最优的,因为$k\ge 2$时,EUCLID$(F_{k+1},F_k)$正好调用了$k$次

$F_k$约为$\phi^k/\sqrt{5}$, $\phi=(1+\sqrt{5})/2$
EUCLID执行中递归调用的次数为$O(\lg b)$
如果EUCLID作用于两个$\beta$位数,则将执行$O(\beta)$次算术运算和$O(\beta^3)$次位操作

扩展形式

用于计算满足下列条件的整系数$x$和$y$(可能为0或负数):
$$d=gcd(a,b)=ax+by$$

运行时间与EUCLID相同

模运算

群论复习

模$n$加法群

你懂的

模$n$乘法群

$$(\mathbb{Z}_n^*, \cdot_n)$$

$$\mathbb{Z}_n^*={[a]_n\in\mathbb{Z}_n: gcd(a,n)=1}$$

定理31.13: 模$n$乘法群是有限交换群

$\mathbb{Z}_n^*$中的除法由等式$a/b\equiv ab^{-1}\pmod n$定义

$\mathbb{Z}n^*$的规模表示为欧拉phi函数($\phi(n)$)
$$\phi(n)=n\prod\limits
{p:\text{p is prime and }p\mid n}(1-\frac{1}{p})$$
直观理解(类似筛法求质数思想):开始有一张$n$个余数组成的表,然后对于每个能整除$n$的素数$p$,在表中划掉所有$p$的倍数。

  • 若$p$是素数,则$\phi(p)=p-1$
  • 若$n$是合数,$$\frac{n}{e^\gamma\ln\ln n+\frac{3}{\ln\ln n}}<\phi(n)<n-1$$($n\ge 3$, $\gamma=0.5772156649\cdots$是欧拉常数)
    • $n>5$时有个更松弛的下界$$\phi(n)>\frac{n}{6\ln\ln n}$$

子群

定理31.14: 一个有限群的非空封闭子集是一个子群

定理31.15(拉格朗日定理): 如果$(S,+)$是一个有限群,$(S’,+)$是$(S,+)$的一个子群,则$|S’|$是$|S|$的一个约数

推论31.16: 如果$S’$是$S$的有限子群,则$|S’|\le |S|/2$

循环群

定理31.17: 对任意有限群$(S,+)$和任意$a\in S$, 一个元素的阶等于它所生成的循环子群的规模,即$ord(a)=|\langle a\rangle|$

$a^{(0)}=e, a^{(i)}=a^{(i\bmod t)}(t=\bmod a)$

推论31.18: 序列$a^{(1)},a^{(2)},\cdots$是周期序列,其周期为$t=\bmod a$, 即$a^{(i)}=a^{(j)}$当且仅当$i\equiv j\pmod t$

推论31.19: 如果$(S,+)$是具有单位元$e$的有限群,则对所有$a\in S$,$a^{(|S|)}=e$

求解模线性方程

问题

$$ax\equiv b\pmod n$$
假设已知$a,b$和$n$,求出所有满足上述方程的对模$n$的$x$的值
该方程可能无解、仅有一解或有多解

数学准备

定理31.20: 对任意正整数$a$和$n$,如果$d=gcd(a,n)$, 则在$\mathbb{Z}_n^*$中,$$\langle a\rangle=\langle d\rangle={0,d,2d,\cdots,((n/d)-1)d}$$
因此,$|\langle a\rangle|=n/d$.

推论31.21: 当且仅当$d\mid b$时,方程$ax\equiv b\pmod n$对于未知量$x$有解。这里$d=gcd(a,n)$.
i.e. 当且仅当$[b]\in\langle a\rangle$时,方程有解

推论31.22: 方程$ax\equiv b\pmod n$或者对模$n$有$d$个不同的解,或者无解。这里$d=gcd(a,d)$.

定理31.23: 令$d=gcd(a,n)$, 假设对某些整数$x’$和$y’$,有$d=ax’+ny’$(例如EXTENDED-EUCLID所计算出的结果)。如果$d\mid b$,则方程$ax\equiv b\pmod n$有一个解的值为$x_0$,这里$x_0=x’(b/d)\pmod n$.

定理31.24: 假设方程$ax\equiv b\pmod b$有解(即$d\mid b$),且$x_0$是该方程的任意一个解。因此,该方程对模$n$恰好有$d$个不同的解,分别为$x_i=x_0+i(n/d)$, 这里$i=0,1,\cdots,d-1$.

伪代码

运行时间

执行$O(\lg n+gcd(a,n))$次算术运算

推论31.25: 对任意$n>1$, $a$和$n$互质时方程对模$n$有唯一解

推论31.26: 对任意$n>1$,若$a,n$互质,则方程$ax\equiv 1\pmod n$对模$n$有唯一解,否则方程无解。
因此,当$a$和$n$互质时,可以用记号$a^{-1}\bmod n$表示$a$对模$n$的乘法逆元

中国余数定理

定理31.27(中国余数定理): 令$n=n_1n_2\cdots n_k$,其中因子$n_i$两两互质。考虑以下对应关系:$$a\leftrightarrow(a_1,a_2,\cdots,a_k)$$这里$a\in\mathbb{Z}_n,a_i\in\mathbb{Z}_{n_i}$, 而且对$i=1,2,\cdots,k$, $$a_i=a\bmod n_i$$.

该映射是一个在$\mathbb{Z}n$ 与笛卡尔积 $\mathbb{Z}{n_1}\times\mathbb{Z}_{n_2}\times\cdots\times\mathbb{Z}_{n_k}$之间的一一对应,对$\mathbb{Z}_n$中元素所执行的运算可以等价地作用于对应的$k$元组

从$(a_1,a_2,\cdots,a_k)$计算$a$:

  • 定义$m_i=n/n_i=n_1n_2\cdots n_{i-1}n_{i+1}\cdots n_l$
  • 对$i=1,2, \cdots l$, 定义$c_i=m_i(m_i^{-1}\bmod n_i)$
    • In fact, $c_i\leftrightarrow(0,0,\cdots ,0,1,0,\cdots 0)$ 除了在$i$个坐标上为1外其余坐标均为0
  • $a\equiv (a_1c_1+a_2c_2+\cdots +a_kc_k)\pmod n$

对任意$x$和$i=1,2,\cdots k,$有$x\bmod n_i=(x\bmod n)\mod n_i$.

推论31.28: 如果$n_1,n_2,\cdots ,n_k$两两互质,$n=n_1n_2\cdots n_k$,则对任意整数$a_1,a_2,\cdots ,a_k$, 关于未知量$x$的联立方程组$$x\equiv a_i\pmod n_i,i=1,2,\cdots k$$对模$n$有唯一解

推论31.29: 如果$n_1,n_2,\cdots ,n_k$两两互质,$n=n_1n_2\cdots n_k$, 则对所有整数$x$和$a$,$x\equiv a\pmod {n_i}$(其中$i=1,2,\cdots k$)当且仅当$x\equiv a\pmod n$.

可以把模大数的线性方程转换为模小数的线性方程组

元素的幂

定理31.30: 对于任意整数$n>1$, $a^{\phi(n)}\equiv 1\pmod n$对所有$a\in\mathbb{Z}_n^*$都成立

定理31.31: 若$p$是素数,则$a^{p-1}\equiv 1\pmod p$对所有$a\in\mathbb{Z}_p^*$都成立

定理31.32: 对所有素数$p>2$和所有正整数$e$,使得$\mathbb{Z}_n^*$是循环群的$n>1$的值为2,4,$p^e$和$2p^e$。

若$g$是$\mathbb{Z}_n^$的生成元,则对于任意$a\in\mathbb{Z}_n^$存在一个$z$,使得$g^z\equiv a\pmod n$. 这个$z$称为对模$n$到基$g$上的$a$的一个离散对数指数,记为$ind_{n,g}(a)$

定理31.33(离散对数定理): 如果$g$是$\mathbb{Z}_n^*$的一个生成元,则当且仅当等式$x\equiv y\pmod {\phi(n)}$ 成立时,有等式$g^x\equiv g^y\pmod n$成立。

定理31.34: 如果$p$是一个奇素数且$e\ge 1$,则方程$$x^2\equiv 1\pmod {p^e}$$仅有两个解,即$x=\pm 1$。

如果$x$满足$x^2\equiv 1\pmod n$, 但$x$不等于以$n$为模的两个平凡平方根,则$x$是一个以$n$为模的非平凡平方根

推论31.35: 如果对模$n$存在1的非平凡平方根,则$n$是合数

快速幂

又名:用反复平方法求数的幂

$c$只是用来辅助正确性证明的变量

循环不变式:

  • $c$的值与$b$的二进制表示的前缀$\langle b_k,b_{k-1},\cdots b_{i+1}\rangle$相同
  • $d=a^c\pmod n$

时间复杂度$O(\beta^3)$

CATALOG
  1. 1. 输入规模和算数计算的代价
  2. 2. 基础数论概念
    1. 2.1. 整除性与约数
    2. 2.2. 素数与合数
    3. 2.3. 除法定理、余数和等模
    4. 2.4. 公约数与最大公约数
    5. 2.5. 互质数
    6. 2.6. 唯一因子分解定理
  3. 3. 最大公约数
    1. 3.1. 欧几里得算法
      1. 3.1.1. 运行时间
      2. 3.1.2. 扩展形式
  4. 4. 模运算
    1. 4.1. 模$n$加法群
    2. 4.2. 模$n$乘法群
    3. 4.3. 子群
    4. 4.4. 循环群
  5. 5. 求解模线性方程
    1. 5.1. 问题
    2. 5.2. 数学准备
    3. 5.3. 伪代码
    4. 5.4. 运行时间
  6. 6. 中国余数定理
  7. 7. 元素的幂
    1. 7.1. 快速幂