tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

扩展欧几里得算法详细举例解析


扩展欧几里得算法
什么是 GCD?
GCD 是最大公约数的简称(当然理解为我们伟大的党也未尝不可)。在开头,我们先下几 个定义: ①a|b 表示 a 能整除 b(a 是 b 的约数) ②a mod b 表示 a-[a/b]b([a/b]在 Pascal 中相当于 a div b)。即有 a|b <=> b mod a=0。 ③gcd(a,b)表示

a 和 b 的最大公约数 ④a 和 b 的线性组合表示 ax+by(x,y 为整数)。我们有:若 d|a 且 d|b,则 d|ax+by(这很重 要!)

线性组合与 GCD
现在我们证明一个重要的定理:gcd(a,b)是 a 和 b 的最小的正线性组合。

例:a=6 b=4,最小正线性组合为 1*a+(-1)*b=2=gcd(a,b)。

证明: 设 gcd(a,b)为 d,a 和 b 的最小的正线性组合为 s ∵d|a 且 d|b, ∴d|s。 而 a mod s=a-[a/s]s =a-[a/s](ax+by) =a(1-[a/s]x)-b[a/s]y 亦为 a 和 b 的线性组合 ∵a mod s<s,a mod s 不能是 a 和 b 的最小的正线性组合 ∴a mod s=0,即 s|a 同理由 s|b ∴s 为 a,b 的公约数 ∴s<=d ∵d|s ∴d=s。证毕。

-1-

由这条定理易推知:若 d|a 且 d|b,则 d|gcd(a,b)

Euclid 算法
现在的问题是如何快速的求 gcd(a,b)。穷举明显不是一个好方法(O(n)),所以需要一个更 好的方法。 首先我们先提出一个定理:gcd(a,b)=gcd(b,a-bx)(x 为正整数)。 证明: 设 gcd(a,b)=d,gcd(b,a-bx)=e,则 ∵d|a,d|b ∴d|a-bx ∴d|gcd(b,a-bx),即 d|e ∵e|b,e|a-bx ∴e|bx+(a-bx),即 e|a ∴e|gcd(a,b),即 e|d ∴d=e。证毕。 这个定理非常有用,因为它能快速地降低数据规模。 当 x=1 时,gcd(a,b)=gcd(b,a-b)。这就是辗转相减法。 当 x 达到最大时,即 x=[a/b]时,gcd(a,b)=gcd(b,a mod b)。这个就是 Euclid 算法。它是不是 Euclid 提出的我不知道,但听说是在 Euclid 时代形成的,所以就叫 Euclid 算法了。程序非 常的简单: function Euclid(a,b:longint):longint; begin if b=0 then exit(a) else exit(Euclid(b,a mod b)); end; Euclid 算法比辗转相减法好,不仅好在速度快,而且用起来也方便。两种算法都有一个隐含 的限制:a>=b。用辗转相减法时,必须先判断大小,而 Euclid 算法不然。若 a<b,则一次递 归就会转为 gcd(b,a),接着就能正常运行了。

扩展 Euclid
前面我们说过,gcd(a,b)可以表示为 a 和 b 的最小的正线性组合。现在我们就要求这个最小 的正线性组合 ax+by 中的 x 和 y。这个可以利用我们的 Euclid 算法。 从最简单的情况开始。 当 b=0 时,我们取 x=1,y=0。 例:a=5,b=0,最小正线性组合为 5*1+y*0=5,y 为任意整数。这里为方便起见规定此时 y=0。

-2-

当 b≠0 时呢? 假设 gcd(a,b)=d,则 gcd(b,a mod b)=d。若我们已经求出了 gcd(b,a mod b)的线性组合表示 bx'+(a mod b)y',则 gcd(a,b)=d =bx'+(a mod b)y' =bx'+(a-[a/b]b)y' =ay'+b(x'-[a/b]y') 那么,x=y',y=x'-[a/b]y'。这样就可以在 Euclid 的递归过程中求出 x 和 y。 程序: function gcd(a,b:longint):longint; var p,n:longint; begin if b=0 then begin x:=1; y:=0; exit(a); end else begin p:=gcd(b,a mod b); n:=x; x:=y; y:=n-a div b*y; exit(p); end; end; 我们现在还有一个问题: 是不是确定的?答案: x,y 不是。 如果 x,y 符合要求, 那么 x+bk,y-ak 也符合要求。不确定的原因在于这一句:“当 b=0 时,我们取 x=1,y=0。”实际上 y 可以取任 何正整数。 以 gcd(26,15)为例: (26,15) (15,11) (11,4) (4,3) (3,1) (1,0) X=-4 Y=3-1*(-4)=7 26*(-4)+15*7=1 X=3 Y=-1-1*3=-4 15*3+11*(-4)=1 X=-1 Y=1-2*(-1)=3 11*(-1)+4*3=1 X=1 Y=0-1*1=-1 4*1+3*(-1)=1 X=0 Y=1-3*0=1 3*0+1*1=1 X=1 Y=0 1*1+0*0=1



-3-

不定方程 ax+by=c
现在终于到了本文重点:解二元一次不定方程。看起来扩展 Euclid 算法是不定方程的一种 特殊情况,实际上呢,不定方程却是用 Euclid 算法解的。 对于不定方程 ax+by=c,设 gcd(a,b)=d,如果 ax+by=c 有解,则 d|c(这也是许多奥数题的切 入点)所以一旦 d 不是 c 的约数, 。 那么 ax+by=c 一定无解。 d|c 时, 当 先求出 ax’+by’=d=gcd(a,b) 的 x'和 y', 由于已经有 ax’+by’=d, 要求 ax’+by’=c, 将整个式子同乘 c/d 倍即可。 x=x'*c/d, 则 y=y'*c/d。由上一段可知, 只要 ax+by=c 有一个解,它就有无数个解。 Euclid 算法还可以求解同余方程 ax≡b(mod m)及其最小 x。这其实和不定方程 ax+my=b 没有 区别。(不定方程和同余方程一般都有范围限制,这其实也很容易解决,就不说了)

其他
初等数论中最基础的就是 GCD 以及其相关问题了。实际上,更深层次的初等数论还包括: ◆中国剩余定理 ◆Miller-Rabin 素性测试 ◆pollard rho 算法

Jollwish 原创,转载请说明出处

Htfy96@qq.com 修改于 2012/11/21

-4-


推荐相关:

RSA算法中的欧几里德算法

(a,p) = d 所以 d | 1 所以 d 只能为 1 扩展欧几里德算法举例举例同上,在 RSA 算法中要求 ed=1(mod Φ(n))即求密钥 d 的模 Φ(n)乘法逆元,即...


算法设计与分析第二版课后习题解答

算法设计与分析基础课后练习答案习题 1.1 4.设计一...b.有a可知计算gcd(31415,14142)欧几里德算法做了...的模式构成的实例,它是蛮力字符串匹配 算法的一个...


扩展欧几里德算法求逆元

扩展欧几里德算法求逆元_计算机硬件及网络_IT/计算机_专业资料。 扩展欧几里德...举例:求 12 模 67 的逆元。 由于 gcd(12, 67) = 1,故其逆元存在且...


算法设计与分析基础习题参考答案

详细的讨论), 我们只考虑这样的问题: 欧几里得算法...比较拗口,举个例子,序列 5 8 5 2 9, 我们知道...(n)=扩展树中内部结点+外部结点=n+(n+1) =2n...


基本算法语句与算法案例练习题(习题经典,有详细解答)

算法” ,其中可以同欧几里得 辗转相除法相媲美的是( A、中国剩余定理 ) C...4.【解析】选 B。 5.【解析】选 C。 6.【解析】选 D。 7.【解析】选...


ACM数论基础之扩展欧几里德详细证明

扩展欧几里德算法扩展欧几里德算法是用来在已知 a,...“中国余数定理”相关知识举个例子比如 n 除以 5 ...2014年建筑幕墙建筑装饰行业分析报告文档贡献者 kku28...


基于扩展欧几里得算法的多项式互素

完成多项式技术后,将其运 用到多项式的扩展欧几里得算法中,实现对两个多项式寻找到使 u(x)f(x)+v(x)g(x)=1 成立的 v(x),u(x); 以下是多项式程序。 ...


RSA算法从数学基础到实例全面解1

RSA 算法从数学基础到实例全面解析分类: 算法 2011-11-20 21:59 148 人阅读...5、扩展欧几里得算法 、作为欧几里得算法的扩展,寻找的是满足 ax + by = gcd(...


RSA算法的数论基础分析

RSA 算法的数论基础分析摘要:RSA 算法作为目前使用最广泛的一种非对称密码算法,...??,还有扩展欧几里得 算法,除了用来计算 gcd 之外,还能计算以下形式的线性组合...


C语言实现欧几里得算法和扩展欧几里得算法

C语言实现欧几里得算法和扩展欧几里得算法_数学_自然科学_专业资料。C语言实现欧几里得算法和扩展欧几里得算法 1、欧几里得算法 1.1 原理阐述欧几里得算法求最大公约数...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com