中国剩余定理(CRT)证明与应用
问题定义
给定一组同余方程:
\[(S):\begin{cases}x≡a_1(\text{mod }m_1)\\x≡a_2(\text{mod }m_2)\\……\\x≡a_n(\text{mod }m_n)\\\end{cases} \]求解此关于 \(x\) 的方程组的最小非负整数解。同余
方程中整数\(m_1,m_2…m_n\)互质。
基本结论
设 \(M=∏_{i=1}^nm_i\) 是整数 \(m_1,m_2…m_n\) 的乘积,并设 \(M_i=\frac{M}{m_i} ,∀i∈\{x∈N^* |1≤x≤n\}\) 是除 \(m_i\) 之外的其余 \((n-1)\) 个整数的乘积。设\(t_i=m_i^{-1}\) 为 \(M_i\) 的数论倒数(对 \(m_i\) 取模意义下的逆元),即满足 \(M_i t_i=1(\text{mod }m_i ),∀i∈\{x∈N^* |1≤x≤n\}\)。
方程组 \((S)\) 的通解形式表示为:
\[x=kM+∑_{i=1}^na_it_iM_i,k∈Z \]在对 \(M\) 取模的意义下,方程组(S)存在唯一解 \(x=(∑_{i=1}^na_it_iM_i) \text{mod }M\)。
证明过程
因为问题定义中限制了整数 \(m_1,m_2…m_n\) 互质的性质,所以可得对于任何正整数 \(i∈\{x∈N^* |1≤x≤n\}\),由于 \(∀j∈\{x∈N^* |1≤x≤n\},j≠i\),则得到 \(gcd(m_i,m_j)=1\) ,即 \(gcd(m_i,M_i )=1\) 。
根据 \(m_i\) 与 \(M_i\) 互质的性质与逆元的存在条件,可知必然存在整数 \(t_i\) 是\(M_i\) 模 \(m_i\) 的逆元,即满足\(M_i t_i=1(\text{mod } m_i )\)。
结合上面推导出的两条结论可以进一步得到如下恒等式:
\[a_iM_it_i≡a_i(\text{mod }m_i),∀j∈\{x∈N^* |1≤x≤n\},j≠i,a_iM_it_i≡0(\text{mod } m_j) \]根据上述恒等式可以得出,对于一个正整数\(x=∑_{i=1}^na_iM_it_i\),其必然满足如下条件:
\[∀i∈\{x∈N^* |1≤x≤n\},x=a_iM_it_i+∑_{j≠i}^na_jM_jt_j≡a_i(\text{mod }m_i) \]说明此时的 \(x\) 为方程组 \((S)\) 的一个解。由此,我们进一步假设 \(x_1,x_2\) 都是方程组 \((S)\) 的解,那么这两个数必然满足 \(∀i∈\{x∈N^* |1≤x≤n\},x_1-x_2≡0(\text{mod } m_i)\)。
又由于整数 \(m_1,m_2…m_n\) 两两互质,则 \(M|(x_1-x_2)\),即 \(x_1,x_2\) 必然相差 \(M\) 的整数倍。而方程组 \((S)\) 特解为 \(x=∑_{i=1}^na_it_iM_i,k∈Z\),由此可得其通解 \(x=kM+∑_{i=1}^na_it_iM_i,k∈Z\)。
扩展欧几里得算法(Exgcd)证明与应用
问题定义
给定一个不定方程 \(ax+by=\text{gcd}(a,b)\),要求求其整数解。
基本结论
根据欧几里得算法,通过对辗转相除法过程中产生式子的收集,可以反代入原方程求出所有整数解。
具体而言,只要对原方程求解出了一组特解 \(x_0,y_0\),就可以得到所有通解的表达式:
\[\begin{cases}x=x_0+t\frac{b}{gcd(a,b)}\\y=y_0-t\frac{b}{gcd(a,b)}\end{cases},t\in N^* \]数学证明
对于不定方程 \(ax+by=\text{gcd}(a,b)\) ①,假设先前已经求得另一个不定方程的解 \(x_1,y_1\) 满足\(bx_1+(a\text{ mod }b)y_1=\text{gcd}(a,b)\) ②,则联立 ①② ,必然可得到 \(ax+by=bx_1+(a\text{ mod }b) y_1\) ③。
由对模运算的分析我们可以知道,模运算实质是被除数与除数与商进行减法运算的过程,即 \(a \text{ mod } b=a-b[\frac{a}{b}]\)。那么 \(ax+by=bx_1+(a\text{ mod }b) y_1\) ③就可以作如下转换:
\[ax+by=bx_1+(a\text{ mod }b)y_1 \]\[⇒ax+by=bx_1+ay_1-b[\frac{a}{b}]y_1 \]\[⇒ax+by=ay_1+b(x_1-[\frac{a}{b}]y_1) \]设 \(⇒ax+by=ay_1+b(x_1-[\frac{a}{b}]y_1)\) 为④式
对比③④两式,可以得到 \(\begin{cases}x=y_1\\y=x_1-[\frac{a}{b}] y_1\end{cases}\)。当前求 \(x,y\) 的问题就转化为了求出满足 \(bx_1+(a\text{ mod }b)y_1=\text{gcd}(a,b)(2)\) 的整数解 \(x_1,y_1\)。根据最大公约数的基本性质可以知道 \(\text{gcd}(a,b)=\text{gcd}(b,a\text{ mod }b)\),那么 \(x_1,y_1\) 所满足的 \(bx_1+(a\text{ mod }b) y_1=\text{gcd}(a,b)\) ②就可以转化为形如 \(ax+by=\text{gcd}(a,b)\) ①的不定方程,在此基础上又可以得到下一个 \(x_2,y_2\) 用于求解\(x_1,y_1\)。如此一来,这个问题的求解就成了一个具有递归性质的过程。
与传统欧几里得算法类似在这个递归过程中,方程参数a,b会被不断互相替换为 \(b,a\text{ mod }b\),以此类推,最终必然会出现 \(a_k=\text{gcd}(a,b),b_k=0\) 的情况,此时的方程为 \(a_kx_k=\text{gcd}(a_k,b_k)\),由于 \(b_k=0\),所以\(\text{gcd}(a_k,b_k)=a_k\),即 \(a_kx_k=a_k\),此时 \(x_k=1,y_k∈R\) 。此时将 \(x_k,y_k\) 反代入上一个方程,即可最终得到特解 \(x_0,y_0\)。
乘法逆元求法概述
问题定义
乘法逆元,是指数学领域群 \(G\) 中任意元素a,都在G中有唯一的逆元 \(a'\),使得 \(aa'=a' a=e\),其中 \(e\) 为该群中的单位元。
简而言之,对于两个整数 \(n,p\),使得 \(nx=1(\text{mod }p)\) 的 \(x\) 即为 \(n\) 在模 \(p\) 意义下的逆元。
基本结论
扩展欧几里得算法(Exgcd)
通过将 \(nx≡1(\text{mod }p)\) 转化为 \(nx+py=1\),即可用扩展欧几里得算法解决(此处 \(\text{gcd}(n,p)=1\),说明 \(n,p\) 互质)。只需要对原方程求解出了一组特解 \(x_0,y_0\),就可以得到所有通解的表达式:
\[\begin{cases}x=x_0+t\frac{b}{gcd(a,b)}\\y=y_0-t\frac{b}{gcd(a,b)}\end{cases},t\in N^* \]费马小定理
对于整数 \(n,p\),若 \(p\) 为质数,且 \(p∤n\),则有 \(n^{p-1}≡1(\text{mod }p)\),\(n\) 在对 \(p\) 取模意义下的逆元即为 \(n^{p-2}\)。
线性乘法逆元算法
对于任意一串整数中的一个数 \(n\),其在模 \(p\) 意义下的逆元为 \(n^{-1}=\begin{cases}1(\text{mod }p),n=1\\-[\frac{p}{n}] (p\text{ mod }n)^{-1}(\text{mod }p),n≠1\end{cases}\),此方法可以在线性时间复杂度内求解一串连续整数中每一个数在模 \(p\) 意义下的乘法逆元
数学证明
扩展欧几里得算法(Exgcd)
见上。
费马小定理
引理1:给定任意三个整数 \(a,b,c\) 和正整数 \(m\),并且满足 \(\text{gcd}(m,c)=1\),则当 \(ac≡bc(\text{mod }m)\)时,\(a≡b(\text{mod }m)\)。原因是由 \(ac≡bc(\text{mod }m)\) 可得 \(ac-bc≡0(\text{mod }m)\),由于 \(m,c\) 互质,所以得到 \(a-b≡0(\text{mod }m)\),即 \(a≡b(\text{mod }m)\)。
·引理2:一对正整数 \(m,n(m>1\text{且} \text{gcd}(m,n)=1)\),构造模 \(m\) 的完全剩余系 \(M=\{a_1,a_2,a_3…a_m\}\),则
\(M'=\{na_1,na_2,na_3…na_m\}\)也构成模 \(m\) 的完全剩余系。原因是若完全剩余系M中存在 \(na_i,na_j\) 模 \(m\) 同余,即 \(na_i≡na_j(\text{mod }m)\),根据引理1则可得 \(a_i≡a_j(\text{mod }m)\),再根据完全剩余系的定义可以知道不存在上述情况,因此不存在 \(na_i,na_j\) 模 \(m\) 同余,该引理得证。
构造模 \(p\) 的完全剩余系 \(P=\{1,2,…p\}\),由于 \(n,p\) 互质,故由引理2可以得到 \(P'≡\{n,2n,3n…pn\}\)也构成模 \(p\) 的完全剩余系。根据完全剩余系的性质可以将上述 \(P\) 与 \(P'\) 中的所有元素分别相乘可以得到 \(1×2×3…×p≡n·2n·3n…pn(\text{mod }p)\),即 \(p!≡n^{p-1}p!(\text{mod }p)\),将等号两端 \(p\) 消去后即得到\(n^{p-1}≡1(\text{mod }p)\),结论得证。
线性逆元算法
首先不难直接知道 \(1^{-1}≡1(\text{mod }p)\)。
设 \(p=kn+r(1<r<n<p)\),此时 \(k\) 为 \(n\) 除 \(p\) 的商,\(r\) 为余数。将这个式子代入模 \(p\) 的意义下就可以得到\(kn+r≡0(\text{mod }p)\) ①。在①恒等号两端乘上 \(n^{-1},r^{-1}\),则可以得到 \(kr^{-1}+n^{-1}≡0(\text{mod }p)\),即 \(n^{-1}≡-kr^{-1}(\text{mod }p)\),将 \(k,r\) 分别以 \(p=kn+r(1<r<n<p)\) 的变型式的形式表示后就得到 \(n^{-1}≡-[\frac{p}{n}] (p\text{ mod }n)^{-1}(\text{mod }p)\)。但特殊地,\(1\) 可以作为 \(1\) 模任何整数意义下的乘法逆元。结论得证。
米勒-拉宾素性测试算法证明与应用
问题定义
给定一个正整数 \(n\),要求判断其是否为素数。
对于给定一个正整数 \(n\),若对\(a,d,r(a,d,r∈N^* ,a,d<n,r∈[0,s-1],n-1=2^s×d)\)都满足 \(\begin{cases}a^d≠1(\text{mod }n)\\a^{2^rd}≠n-1(\text{mod }n)\end{cases}\) 中的一种情况,则可以判断 \(n\) 为合数。反之,则可以判定 \(n\) 为素数。
数学证明
根据费马小定理可知,对于一个素数 \(n\),必然有\(a(a∈N^* )\)满足 \(a^{n-1}≡1(\text{mod }n)\)。
假设 \(n\) 是一个奇素数,那么 \(n-1\) 必然为偶数,即可以表示为 \(2^s×d(s,d∈N^* )\)的形式,那么其对于 \(a(a∈N^* )\),必然满足\(\begin{cases}a^d≡1(\text{mod }n)\\a^{2^rd}≡n-1(\text{mod }n)\end{cases}\)。由此,结合费马小定理的内容,若我们不断对 \(n-1\) 进行开平方根的操作,则必然得到在对 \(n\) 取模意义下的 \(1\) 或 \(-1\)。也就是说,若找到任意一个\(a(a∈N^* )\)满足\(\begin{cases}a^d≠1(\text{mod }n)\\a^{2^rd}≠n-1(\text{mod }n)\end{cases}\),那么 \(n\) 就不是一个素数,\(a\) 被称为 \(n\) 是合数的一个凭证(witness)。
但通过对部分特殊 \(n\) 的分析,可以发现并不是所有通过一次测试的 \(n\) 都是素数:对于部分合数 \(n\),也有概率能通过上述测试,此时的 \(a\) 称为证明 \(n\) 是素数的强伪证(strong liar)。在实际算法设计中,由于无法知道 \(n\) 的所有强伪证在 \([1,n-1]\) 的具体分布,需要多次随机选取基数 \(a\) 进行测试。
注意事项
由于米勒-拉宾素性测试算法只针对奇素数,所以在实际应用中要对素数 \(2\) 进行特判。
标签:总结,专题,gcd,数论,text,逆元,na,cases,mod From: https://www.cnblogs.com/frkblog/p/16747868.html