1
1
2016
0

简单数论算法


一些很基础的数论算法。

数学太弱了,写得烂,没什么办法。

本文大量参考、引用《算法导论》第31章内容。


基础概念

$d\mid a$表示$\exists k\in\mathbb{Z},a=kd$,即$d$整除$a$。称$a$为$d$的倍数。对于$d>0$,$d$为$a$的因数(也叫约数)。$d\nmid a$表示$d$不能整除$a$。

如果一个整数$a>1$只能被$1$和它自己整除,那么这个数是质数(也叫素数),否则称它为合数,$1$为基本单位,不是质数也不是合数。

对于任意$a\in\mathbb{Z},n\in\mathbb{N}^+$,存在唯一的$q,r\in\mathbb{Z}$,满足$r\in\left[0,n\right),a=qn+r$。其中$q=\left\lfloor a/n\right\rfloor$为除法的商,$r=a\bmod b$为除法的余数。$n\mid a$当且仅当$a\bmod n=0$。

根据整数模$n$的余数,可以将所有整数划分为$n$个等价类。包含整数$a$模$n$的等价类为$\left[a\right]_n=\left\{a+kn|k\in\mathbb{Z}\right\}$。所有这类等价类的集合为$\mathbb{Z}_n=\left\{\left[a\right]_n|a\in\left[0,n\right)\right\}$。一般用每个等价类的最小非负元素来代表它,即用$0$代表$\left[0\right]_n$等。

若$d$是$a$的因数且$d$是$b$的因数,则$d$是$a$与$b$的公因数。$1$是任意两个整数的公因数。

公因数的两条重要性质:

对于任意$x,y\in\mathbb{Z}$,若$d\mid a,d\mid b$,则有$d\mid\left(ax+by\right)$。
对于任意$a,b\in\mathbb{Z}$,若$a\mid b$且$b\mid a$,则有$a=\pm b$。

两个不同是为$0$的整数$a,b$的最大的公因数称为最大公因数,记作$\gcd\left(a,b\right)$。

$\gcd$的一个重要性质:对于任意不为$0$的整数$a,b$,$\gcd\left(a,b\right)$是$a$与$b$的线性组合集$\left\{ax+by|x,y\in\mathbb{Z}\right\}$中的最小正元素。

简单证明:

设$s$为$a$与$b$的线性组合集中的最小正元素,且对于某个$x,y\in\mathbb{Z}$,有$s=ax+by$。设$q=\left\lfloor a/s\right\rfloor$。
显然有$a\bmod s=a-qs=a\left(1-qx\right)+b\left(-qy\right)$。所以$a\bmod s$也是$a$与$b$的一个线性组合。由于$s$是这个线性组合集中的最小整数,且$a\bmod s\in\left[0,s\right)$,所以$a\bmod s=0$,即有$s\mid a$。类似地,有$s\mid b$。所以$s$是$a,b$的公因数,$\gcd\left(a,b\right)\geq s$。
因为$\gcd\left(a,b\right)\mid a,\gcd\left(a,b\right)\mid b,s=ax+by$,由上面提到的公因数的性质可知$\gcd\left(a,b\right)\mid s$。又因为$s>0$,所以$\gcd\left(a,b\right)\leq s$。
结合起来,可得$\gcd\left(a,b\right)=s$。

下面是几个简单的推论。

对于任意$a,b\in\mathbb{Z}$,若$d\mid a$且$d\mid b$,则有$d\mid\gcd\left(a,b\right)$。
对于任意$a,b\in\mathbb{Z},n\in\mathbb{N}$,有$\gcd\left(an,bn\right)=n\gcd\left(a,b\right)$。
对于任意$a,b,n\in\mathbb{N}^+$,若$n\mid ab$且$\gcd\left(a,n\right)=1$,有$n\mid b$。

对于任意$a,b\in\mathbb{Z}$,若有$\gcd\left(a,b\right)=1$,则称$a,b$为互质数。若两个整数分别与一个整数$p$互质,则它们的积与$p$互质。

对于一组整数$n_1,n_2,...,n_k$,若有$\gcd\left(n_i,n_j\right)=1\left(i\neq j\right)$,则称他们两两互质。

关于质数整除性的一个重要事实:若对于任意质数$p$和任意整数$a,b$,有$p\mid ab$,则$p\mid a$与$p\mid b$这两者至少有一个成立。

唯一分解定理:合数$a$仅能以唯一一种方式写成如下形式:$$a=p_1^{e_1}p_2^{e_2}...p_r^{e_r}$$

其中$p_i$为质数,$p_1<p_2<...<p_r$,且$e_i\in\mathbb{N}^+$。


最大公因数与欧几里得算法

考虑如何计算$\gcd\left(a,b\right)$。

直接分解质因数的话效率显然是不对的。下面直接给出代码欧几里得算法的代码。

这份代码的正确性基于这个等式$\gcd\left(a,b\right)=\gcd\left(b,a\bmod b\right)$。

下面给出简单证明。

设$d=\gcd\left(a,b\right),d'=\gcd\left(b,a\bmod b\right)$。
显然有$d\mid b$。由于$a\bmod b$是$a,b$的一个线性组合($a\bmod b=a-\left\lfloor a/b\right\rfloor b$),所以有$d\mid a\bmod b$。综合一下,根据前面的一个推论,有$d\mid d'$。
用类似的方法,易证$d'\mid d$。
最终得到$d=d'$。

欧几里得算法的运行时间与斐波那契数列有关。对于任意整数$k\geq 1$,若$a>b\geq 1$且$b<F_{k+1}$,则用欧几里得算法计算$\gcd\left(a,b\right)$的递归调用次数少于$k$次。其中$F_n$表示斐波那契数列的第$n$项。

可以证明递归调用的次数为$\mathcal{O}\left(\log_2 b\right)$。

复杂度的证明略去(因为我不会)。

下面给出欧几里得算法的扩展形式。

前面证明过$\gcd\left(a,b\right)$是$a,b$的线性组合集中的最小正元素。这份代码不但计算了$\gcd\left(a,b\right)$,也计算了满足$\gcd\left(a,b\right)=ax+by$的整数$x,y$。

下面给出算法正确性的证明。

设$x',y'$为满足$\gcd\left(b,a\bmod b\right)=bx'+\left(a\bmod b\right)y'$的整数。
由于$\gcd\left(a,b\right)=\gcd\left(b,a\bmod b\right)$,所以有$$\gcd\left(a,b\right)=bx'+\left(a\bmod b\right)y'$$$$=bx'+\left(a-\left\lfloor a/b\right\rfloor b\right)y'$$$$=ay'+b\left(x'-\left\lfloor a/b\right\rfloor y'\right)$$
所以取$x=y',y=x'-\left\lfloor a/b\right\rfloor y'$是正确的。


模运算相关

一般情况下,可以将模运算与通常的整数运算一样看待。在执行模$n$运算时,结果值$x$,用集合$\left\{0,1,...,n-1\right\}$中在模$n$的意义下与$x$等价的元素替代。即用$x\bmod n$替代$x$。对于加法、减法和乘法运算,用这样的模型就够了。

下面给出使用群论结构来描述的模运算模型。

群$\left(S,\oplus\right)$是一个集合$S$和定义在$S$上的二元运算$\oplus$(有时$\oplus$在上下文中显然,就可以只用$S$来表示一个群),该运算满足:

  1. 封闭性:$\forall a,b\in S,\ a\oplus b\in S$;
  2. 单位元:$\exists e\in S,\ \forall a\in S,e\oplus a=a\oplus e=a$,$e$称为群的单位元;
  3. 结合律:$\forall a,b,c\in S,\ \left(a\oplus b\right)\oplus c=a\oplus\left(b\oplus c\right)$;
  4. 逆元:$\forall a\in S,\ \exists!\ b\in S,a\oplus b=b\oplus a=e$,$b$称为$a$的逆元。

若群$\left(S,\oplus\right)$满足交换律,即$\forall a,b\in S,\ a\oplus b=b\oplus a$,则它是一个交换群。若群$\left(S,\oplus\right)$满足$\left|S\right|<\infty$,则它是一个有限群。

通过重新定义整数的加法和乘法运算,可以得到$\mathbb{Z}_n$上的对应运算$+_n,\large\cdot_n$。

$$\left[a\right]_n+_n\left[b\right]_n=\left[a+b\right]_n$$$$\left[a\right]_n\large\cdot_n\left[b\right]_n=\left[ab\right]_n$$

使用新定义的$+_n$,定义模$n$加法群$\left(\mathbb{Z}_n,+_n\right)$,它的规模为$\left|\mathbb{Z}_n\right|$,单位元为$0$,元素$a$的逆元为$-a$。易证该系统是一个有限交换群,证明这里略去。

现在考虑乘法。现在不能使用$\mathbb{Z}_n$了,否则部分元素将没有逆元。定义模$n$乘法群$\left(\mathbb{Z}_n^*,\large\cdot_n\right)$,其中$\mathbb{Z}_n^*=\left\{\left[a\right]_n\in\mathbb{Z}_n|\gcd\left(a,n\right)=1\right\}$,它的单位元为$1$。

关于该系统是有限交换群的证明,其他部分略去,这里仅考虑逆元的存在性证明(唯一性的证明在遥远的下面)。

设$ax+ny=\gcd\left(a,n\right)=1$,那么,等价地,有$ax\equiv 1\pmod n$,所以$x$是$a$的逆元。$ax+ny=1$也同时说明了$x$和$n$的最小正线性组合是$1$,所以$\gcd\left(x,n\right)=1$,所以$x\in\mathbb{Z}_n^*$。

$\mathbb{Z}_n^*$的规模可以用$\phi\left(n\right)$。这个函数称为欧拉$phi$函数,表示与$n$互质的数的个数。

易证$\phi\left(n\right)=n\prod_\limits{p\ is\ prime,p\mid n}\left(1-\frac{1}{p}\right)$。

若$\left(S,\oplus\right)$和$\left(S',\oplus\right)$都是群,且$S'\subseteq\S$,则后者是前者的子群。

子群的另一个判断方法是:若$\left(S,\oplus\right)$是一个有限群,$S'\neq S,S'\subseteq S$,$\forall a,b\in S',a\oplus b\in S'$,则$\left(S',\oplus\right)$是$\left(S,\oplus\right)$的子群。

拉格朗日定理给出了子群规模的一个限制:若$\left(S',\oplus\right)$是$\left(S,\oplus\right)$的一个子群,则$\left|S'\right|$是$\left|S\right|$的因数。

考虑一个生成子群的方法。选择一个元素$a\in S$,根据所有用群上定义的运算取出所有能用$a$生成的元素。

定义$a^{\left(k\right)}=\mathop{\oplus}_\limits{i=1}^\limits{k}=a\oplus a\oplus\cdots\oplus a\left(共k个a\right)$。

那么$a$生成的子群用$\left(\left<a\right>,\oplus\right)$或$\left<a\right>$表示,其中$\left<a\right>=\left\{a^{\left(k\right)}|k\in\mathbb{N}^+\right\}$。$a$称为$\left<a\right>$的生成元。

至于它为什么一定是$S$的子群。因为$\oplus$满足结合律,$a^{\left(i\right)}\oplus a^{\left(j\right)}=a^{\left(i+j\right)}$,所以$\left<a\right>$是封闭的,用前面提到的子群的第二个判断方法即可。

定义在群$S$中的元素$a$的阶为满足$a^{\left(k\right)}=e$的最小整数$k$,记作$ord\left(a\right)$。

显然有$\forall a\in S,\ \left|\left<a\right>\right|=ord\left(a\right)$。

一个推论:$\left|\left<a\right>\right|\mid\left|S\right|\Rightarrow a^{\left(\left|S\right|\right)}=e$。


使用扩展欧几里得算法求解线性同余方程

已知$a,b,n$,求解方程$ax\equiv b\pmod n$。

显然,当且仅当$b\bmod n\in\left<a\right>$时,该方程有解。

设$d=\gcd\left(a,n\right)$。

因为$d$是$a$与$n$的一个线性组合,所以$d\in\left<a\right>$。所以有$\left<d\right>\subseteq\left<a\right>$。

同时,对于任意元素$m\in\left<a\right>$,显然$m$是$a$和$n$的一个线性组合。再由$d\mid a,d\mid n$,可以得到$d\mid m$,所以有$m\in\left<d\right>$。等价地,$\left<a\right>\subseteq\left<d\right>$。

综合一下,可以得到当且仅当$d\mid b$时,该方程有解。

假设对于$x',y'\in\mathbb{Z}$,有$ax'+ny'=d$(可以使用扩展欧几里得计算),那么显然有$ax'\left(b/d\right)+ny'\left(b/d\right)=b$(注意因为$b\mid d$,所以$b/d\in\mathbb{Z}$),即$ax'\left(b/d\right)=b\pmod n$。

这样就可以得到方程的一个解。下面证明方程共有$d$个解,它们依次相差$n/d$。

$a\left(x+in/d\right)=ax+ain/d\equiv ax\pmod n$(注意$d\mid a$)

对此有一个有用的推论。

若$\gcd\left(a,n\right)=1$,则方程$ax\equiv b\pmod n$有唯一解,否则无解。(这就证明了$\mathbb{Z}_n^*$中的元素的逆元的唯一性,并说明了该群仅包括与$n$互质的数的原因)

由于这个推论,当$a$与$n$互质时可以用$a^{-1}\bmod n$来表示$a$对模$n$的乘法逆元。

下面给出求解模线性方程的最小正整数解的代码。

同时也可以用这份代码来求乘法逆元,即求解$ax\equiv 1\pmod n$。


中国剩余定理与线性同余方程组

中国剩余定理的内容很简单。

对于$n=n_1n_2\cdots n_k$,其中$n_i$两两互质,有$a\in\mathbb{Z}_n$与$\left(a_1,a_2,\cdots,a_k\right)$(其中$a_i\in\mathbb{Z}_{n_i}$)一一对应。

由$a$求出对应的一组$a_i$很简单,只要分别取模就可以了。

考虑如何由一组$a_i$求$a$。

令$m_i=n/n_i,c_i=m_i\times\left(m_i^{-1}\bmod n_i\right)$。

则有$a=\sum_{i=1}^n a_ic_i$。

显然在模$n_i$时,$c_i=1$(因为逆元),$c_j=0\left(j\neq i\right)$(因为$n_i\mid m_j$)。所以这么做是对的。

中国剩余定理的一个最简单的应用就是求解线性同余方程组。这个很简单,用扩展欧几里得算法分别求解,再用中国剩余定理合并即可。

另一个常见的用法是对于一些要对合数取模的问题,先把模数分解,分别求解,最后再合并。


幂相关与BSGS算法

欧拉定理:$\forall n>1,a\in\mathbb{Z}_n^*,\ a^{\phi\left(n\right)}\equiv 1\pmod n$。

之前已经提到$a^{\left(\left|S\right|\right)}=e$。那么欧拉定理其实就是它在$\mathbb{Z}_n^*$上的特例。

费马小定理:对于质数$n$,$a^{n-1}\equiv 1\pmod n$。

显然这是欧拉定理的一个特例,因为对于质数$n$,有$\phi\left(n\right)=n-1$。

若对于$g\in\mathbb{Z}_n^*$,有$ord\left(g\right)=\mathbb{Z}_n^*$,则$\mathbb{Z}_n^*$中的每个元素都是$g$的一个幂,$g$称为$\mathbb{Z}_n^*$的生成元或原根。如果$\mathbb{Z}_n^*$包含一个原根,就称它是循环的。

对于$\mathbb{Z}_n^*$的原根$g$,以及$a\in\mathbb{Z}_n^*$,存在一个$x$,使得$g^x\equiv a\pmod n$。$x$称为对模$n$到基$g$上的一个离散对数,记作$x=ind_{n,g}\left(a\right)$。

显然,根据欧拉定理,对于$\mathbb{Z}_n^*$的原根$g$,当且仅当$x\equiv y\pmod\phi\left(n\right)$时,有$g^x\equiv g^y\pmod n$。

有一个与离散对数很类似的问题:给出整数$a,b$与质数$n$,求最小的$x$,满足$a^x\equiv b\pmod n$。

设$x=im+j\left(i,j,m\in\mathbb{N}^+,j<i\right)$,那么原式变形为$a^{im}a^j\equiv b\pmod n$。

现在枚举$i$,即可用扩展欧几里得解出$a^j$。只须在枚举$i$之前枚举$j$,预处理出$a^j$的值,并放进哈希表(或其他较快的字典实现)里,就可以在枚举$i$时求出对应的$j$值(如果存在的话)。

由于$n$是质数,根据费马小定理,有$a^x\equiv a^{x\bmod n-1}\pmod n$,所以要求的$x$在$0$到$n-2$中。显然取$m=\left\lceil\sqrt {n-2}\right\rceil$时,$i,j$都只须枚举到$\mathcal{O}\left(\sqrt n\right)$,复杂度最优,也为$\mathcal{O}\left(\sqrt n\right)$。

以上过程就是BSGS算法。

现在考虑$n$是合数的情况,若$\gcd\left(a,n\right)=1$,就问题不大,$a$的幂显然也和$n$互质,直接把$\phi\left(n\right)$求出来,或者仍旧用$n-1$(因为$\phi\left(n\right)<=n-1$)都可以,直接跑BSGS。

但如果$\gcd\left(a,n\right)>1$,那就要麻烦一些。显然对于任意整数$a,b,d,b$,$a\equiv b\pmod n$等价于$ad\equiv bd\pmod {nd}$。考虑从$a^x$中分出$c$个$a$,用它们来和$b,n$消去公因数,这样设$d=\gcd\left(a^c,n\right)$,问题转化为$\left(a^c/d\right)a^{x-c}=b/d\pmod{n/d}$,就可以用BSGS求解了。

因为$n$的因数不超过$\sqrt n$个,所以效率仍旧是$\mathcal{O}\left(\sqrt n\right)$的。

注意解可能会小于$c$,所以要在消去公因数时顺便判断一下。

这里给出代码。


质数测试与整数的因式分解

最朴素的判断质数的方法是试除,但这样做的效率显然不够好。

对于整数$a,n$,若$n$是质数,那么根据费马小定理,$a^{n-1}\equiv 1\pmod n$。

那么很自然地会有这样一个想法:对于合数$n$,任意整数$a$都不满足上面这个等式。

根据这个,可以构造出一个判断素数的方法,即用一个固定的$a$去判断是否满足上面这个等式。

但这是不正确的。对于整数$a$,合数$n$,若满足$a^{n-1}\equiv 1\pmod n$,则$n$称为基为$a$的伪质数。例如$341,561$都是基为$2$的伪质数。在前$10000$个正整数中,基为$2$的伪质数有$22$个。

这样的出错率,在一般的应用中问题不大,但在OI中显然是不行的。

Miller Rabin算法基于这个思想,并对它做了改进。

有这样一个结论:对于奇质数$n$,正整数$e$,方程$x^2\equiv 1\pmod {n^e}$有且仅有两个解,即$x=\pm 1$。

也就是说如果这个等式在模$n$时不成立,那么它一定是合数。

所以可以在计算$a^{n-1}$时,用类似于快速幂的方法,顺便取一些$x$判断这个等式是否成立,以此来降低出错率。

同时,再考虑一个简单的优化,即随机多取几个$a$进行判断。

下面给出Miller Rabin算法的代码。

对于较小的$n$,可以认为它的正确性是有保证的。在OI中,往往不采用随机值,而是测试一组固定的$a$值。

之前提到了可以用试除的方法判断质数,有一个同样可以用试除来做的问题,即整数的因式分解。那么来考虑它有没有什么更高效的算法。

$rho$是一个效率较高,容易理解,实现又简单的用来解决这个问题的算法。尽管它不是现在最快的算法,但基本上已经够用了。

这里就不介绍具体内容了,我在网上找到了一篇很不错的相关介绍,可以去看一看。

英文版:
https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html

中文翻译:
http://wenku.baidu.com/link?url=jV6-ehWxtMFP5vfw0r9lTpgD8ukODq5j9l4X8y6R-IWYLWnNUEfiZRqVPZoepF9XBHna1edl9uoJFRrUDI_DZZS_gDoyyAbq4iWRywVe1dS


例题的话因为这篇太长了,就写在另外一篇里了。

Category: 算法及其他知识 | Tags: 数论 数学 | Read Count: 1005

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com