RSA算法中的欧几里德算法

RSA算法中的欧几里德算法

2008-03-14 12:10 1078人阅读评论(0) 收藏举报欧几里德算法（辗转相除法）

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b

假设d是a,b的一个公约数，则有

d|a, d|b，而r = a - kb，因此d|r

因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则

d | b , d |r ，但是a = kb +r

因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

欧几里德算法举例

例如，在RSA算法中，首先要验证Φ（n）与密钥d互素，则可利用欧几里德算法来验证：

设Φ(n)=(23-1)*(29-1)=616，取d=19，则依次进行如下过程：

616 ÷ 19 = 32 余 8

19 ÷ 8 = 2 余 3

8 ÷ 3 = 2 余 2

3 ÷ 2 = 1 余 1

当余数为1时，即可证明Φ（n）与d互素

扩展欧几里德算法

模P乘法逆元

对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。

定理：a存在模p的乘法逆元的充要条件是gcd(a，p) = 1

证明：首先证明充分性

如果gcd(a，p) = 1，根据欧拉定理，aφ(p) ≡ 1 mod p，因此

显然aφ(p)-1 mod p是a的模p乘法逆元。

再证明必要性

假设存在a模p的乘法逆元为b

ab ≡ 1 mod p

则ab = kp +1 ，所以1 = ab - kp

因为gcd(a，p) = d

所以d | 1

所以d只能为1

扩展欧几里德算法举例

举例同上，在RSA算法中要求ed=1(mod Φ(n))即求密钥d的模Φ(n)乘法逆元，即d=19，

Φ(n)=(23-1)*(29-1)=616

参考“正向”欧几里德算法的计算式，采用回推法

1=3- 1×2

1=3- 1×(8-2×3) 整理，即1=3×3- 1×8

1=3×(19-2×8)- 1×8 整理，即1=3×19- 7×8

1=3×19- 7×(616-32×19) 整理，即1=227×19- 7×616

由此，得到结果：227×9=1 （mod 616），故e=19

分享到：

?上一篇：RSA算法中的欧拉定理和费马定理?下一篇：RSA算法中的高幂次运算实现

欧几里德算法

欧几里得算法的概述 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 欧几里得算法原理 Lemma 1.3.1 若a, b 且 a = bh + r, 其中h, r , 则gcd(a, b) = gcd(b, r). 证明. 假设d1 = gcd(a, b) 且d2 = gcd(b, r). 我们证明d1| d2 且d2| d1, 因而可利用Proposition 1.1.3(2) 以及d1, d2 皆為正数得证d1 = d2. 因d1| a 且d1| b 利用Corollary 1.1.2 我们知d1| a - bh = r. 因為d1| b, d1| r 且d2 = gcd(b, r) 故由Proposition 1.2.5 知d1| d2. 另一方面, 因為d2| b 且d2| r 故d2| bh + r = a. 因此可得d2| d1. Lemma 1.3.1 告诉我们当 a > b > 0 时, 要求a, b 的最大公因数我们可以先将 a 除以 b 所得餘数若為r, 则a, b 的最大公因数等於 b 和r 的最大公因数. 因為0r < b < a, 所以当然把计算简化了. 接著我们就来看看辗转相除法. 由於gcd(a, b) = gcd(- a, b) 所以我们只要考虑a, b 都是正整数的情况. Theorem 1.3.2 (The Euclidean Algorithm) 假设a, b 且 a > b. 由除法原理我们知存在h0, r0 使得 a = bh0 + r0, 其中0r0 < b. 若r0 > 0, 则存在h1, r1 使得 b = r0h1 + r1, 其中0r1 < r0. 若r1 > 0, 则存在h2, r2 使得 r0 = r1h2 + r2, 其中0r2 < r1. 如此继续下去直到rn = 0 為止. 若n = 0 (即r0 = 0), 则gcd(a, b) = b. 若n1, 则gcd(a, b) = rn - 1. 証明. 首先注意若r0 0, 由於r0 > r1 > r2 > ... 是严格递减的, 因為r0 和0 之间最多仅能插入r0 - 1 个正整数, 所以我们知道一定会有nr0 使得rn = 0. 若r0 = 0, 即 a = bh0, 故知 b 為 a 之因数, 得证 b 為a, b 的最大公因数. 若r0 > 0, 则由Lemma 1.3.1 知 gcd(a, b) = gcd(b, r0) = gcd(r0, r1) = ... = gcd(rn - 1, rn) = gcd(rn - 1, 0) = rn - 1. 现在我们来看用辗转相除法求最大公因数的例子 Example 1.3.3 我们求 a = 481 和 b = 221 的最大公因数. 首先由除法原理得481 = 2 . 221 + 39, 知r0 = 39. 因此再考虑 b = 221 除以r0 = 39 得221 = 5 . 39 + 26, 知r1 = 26. 再以r0 = 39 除以r1 = 26 得39 = 1 . 26 + 13, 知r2 = 13. 最后因為r2 = 13 整除r1 = 26 知r3 = 0, 故由Theorem 1.3.2 知gcd(481, 221) = r2 = 13.

解 二 元 一 次 方 程 — — — 拓 展 欧 几 里 得 算 法

欧几里得算法与扩展欧几里得算法（求二元一次不定方程、乘法逆元） 1.欧几里得算法，即辗转相除法。用于求两个整数的最大公约数比较方便，时间复杂度为O（logN）N为两个整数的规模。 最大公约数，是能够同时被两个整数整除的最大整数。 比如说，求56和21的最大公约数：（每行数分别代表a=56,b=21,a%b）此时得到最大公约数为7。 递归代码如下： int gcd(int a, int b) return b ? gcd(b, a%b) : a; 2.扩展欧几里得算法 顾名思义，扩展欧几里得算法就是对欧几里得算法的扩展，可以应用于求二元一次方程的通解、乘法逆元等。 对于上面的欧几里得算法，当递归到出口时，a=7,b=0。很容易就可以得到一组ax+by=7的解：x=1,y=0。 那么如何通过7x+y=7的解逆推出56x+21y=7的解呢？ 对于欧几里得算法的每一个状态，都存在ax+by=gcd(a,b)的解，我们假设有这样两组解（且他们为相邻状态）： ax1+by1=gcd(a,b) a'x2+b'y2=gcd(a',b') 那么可以知道：a'=b b'=a%b 且gcd(a',b')=gcd(b,a%b)=gcd(a,b)，

所以有 ax1+by1=bx2+(a%b)y2 另a%b可写为 a-a-b 所以有 ax1+by1=bx2+(a-(a-b)b)y2 故ax1+by1=ay2+bx2+(a-b)by2 故ax1=ay2 by1 = b(x2+ (a-b)by2) 故 x1=y2 y1 = x2 +(a-b)y2 故可以得到x1,y1与x2,y2的关系 : x1=y2 y1 = x2 +(a-b)y2 我们已知的是最后一组解，那么就要根据最后一组解逆推上去，就可以得到ax+by=gcd(a,b)的一组解了。 代码如下： int exgcd(int a, int b, intx, int y) return a; int r = exgcd(b, a%b, x, y); --递归到求出公约数，开始倒着求每一组的x,y。最后就得到这样一组特解了。 y = t - (a - b)*y; return r; 现在，通过扩展欧几里得算法，可以求出ax+by=gcd(a,b)的一组特解。那么如何求其通解呢？ 3.二元一次方程通解 假设求得的特解为ax0+by0=r ,r=gcd(a,b). ax0+by0+ab*k-ab*k=r a(x0+b*k)+b(y0-a*k)=r

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

扩展欧几里得算法 什么是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

由这条定理易推知：若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

扩展欧几里德算法计算乘法逆元

扩展欧几里德算法计算乘法逆元 一．欧几里德算法 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为： void swap(int & a, int & b) { int c = a a = b; b = c; } int gcd(int a,int b){ if(0 == a ){ return b; } if( 0 == b){ return a; } if(a > b){ swap(a,b); } int c; for(c = a % b ; c > 0 ; c = a % b){

a = b; b = c; } return b; } 二．扩展欧几里德算法乘法逆元 模P乘法逆元 对于整数a、p，如果存在整数b，满足ab mod p =1，则说，b是a的模p乘法逆元。定理：a存在模p的乘法逆元的充要条件是gcd(a,p) = 1 三．扩展欧几里德算法如下： #include int gcd(int a, int b , int &ar,int &br){ int x1,x2,x3; int y1,y2,y3; int t1,t2,t3; int k; if(0 == a){ //有一个数为0，就不存在乘法逆元 ar = 0; br = 0; return b; }

if(0 == b) { ar = 0; br = 0 ; return a; } x1 = 1; x2 = 0; x3 = a; y1 = 0; y2 = 1; y3 = b; for(t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3){ k = x3/y3; t2 = x2-k*y2; t1 = x1-k*y1; x1 = y1; x1 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; }

快速指数取模运算与用扩展欧几里得算法求解最大公约数和求乘法逆元

实验1.1 快速指数取模运算 一、实验1.1源代码： #include "stdio.h" #include "stdlib.h" #include "iostream" using namespace std; void Mode(int a, int b, int n) { int c=1; do{ if(a%2==0) { a=a/2; b=(b*b)%n; } else { a=a-1; c=(b*c)%n; } }while(a!=0); cout<<"取余结果为："<>a; cout<<"请输入该基数b："<>b; cout<<"请输入被除数n："<>n; Mode(a,b,n);

二、实验效果图：

实验1.2 用扩展欧几里得算法求解最大公约数和求乘法逆元 一、实验1.2源代码： #include int extended_Gcd(int a,int b, int &x, int &y) //求最大公约数 { if (b == 0) { x = 1; y = 0; return a; } else { int gcd = extended_Gcd(b, a%b, x, y); int t = x; x = y; y = t - (a / b) * y; return gcd; } } int extended_Ivn(int f, int d, int *result) //求乘法逆元 { int x1, x2, x3, y1, y2, y3, t1, t2, t3, q; x1 = y2 = 1; x2 = y1 = 0; x3 = (f >= d) ? f : d; y3 = (f >= d) ? d : f; while (1) { if (y3 == 0) { *result = x3; // 两个数不互素则result为两个数的最大公约数，此时返回值为零 return 0; } if (y3 == 1) {

欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个正整数a，b的最大公约数。 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（greatest common divisor）缩写为gcd。 辗转相除法的结果条件是两个数取模等于零，即一个数能整除另外一个数时，此时较小的数就是最大公约数 算法思想：(最小公倍数=两个整数之积/最大公约数) (1) 对于已知两数m,n,使得m>n； (2) m除以n得余数r； (3) 若r=0,则n为求得的最大公约数,算法结束；否则执行(4)； (4) m←n,n←r,再重复执行(2). 方法举例理解 1、查找约数法．先分别找出每个数的所有约数，再从两个数的约数中找出公有的约数， 其中最大的一个就是最大公约数．例如，求12和30的最大公约数．12的约数有：1、 2、3、4、6、12；30的约数有：1、2、3、5、6、10、15、30．12和30的公约数 有：1、2、3、6，其中6就是12和30的最大公约数． 2、辗转相除法．当两个数都较大时，采用辗转相除法比较方便．其方法是：以小 数除大数，如果能整除，那么小数就是所求的最大公约数．否则就用余数来除刚才的除数；再用这新除法的余数去除刚才的余数．依此类推，直到一个除法能够整除，这时作为除数的数就是所求的最大公约数．例如：求4453和5767的最大公约数时，可作如下除法．5767÷4453＝1余1314 4453÷1314＝3余511 1314÷511＝2余292 511÷292＝1余219 292÷219＝1余73 219÷73＝3 于是得知，5767和4453的最大公约数是73． 则对于题目中所给按算法思想求出32和24的最大公约数，可按照上面方法进行计算。 32÷24=1 余8 24÷8=3 于是得知，32和24的最大公约数是8.

c++,使用欧几里得算法计算两个数的最大公约数,分别用递推和递归两种算法实现5

实验九 一、实验内容 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10 用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 二、实验目的 1、掌握函数的嵌套调用好递归调用 2、掌握递归算法 3、了解内联函数、重载函数、带默认参函数的定义及使用方法 4、掌握程序的多文件组织 5、掌握编译预处理的内容，理解带参数宏定义与函数的区别 三、实验步骤 教材3.9 定义递归函数实现下面的Ackman函数 n+1 m=0 Acm(m,n)= Acm(m-1,1) n=0 Acm(m-1,Acm(m,n-1)) n>0,m>0 教材3.10用递归法实现勒让德多项式： 1 n=0 Pn= x n=1 ((2n-1)xPn-1(x)-(n-1)Pn-2(x))/n 教程p24 使用欧几里得算法计算两个数的最大公约数，分别用递推和递归两种算法实现 教程p26 编程：将上题以多文件方式组织，在area.h中声明各个area（）函数原型，在area.cpp文件中定义函数，然后在Exp9_2中包含area.h,定义main（） 函数并执行。 四、实验数据及处理结果

同余式的欧几里得算法

同余式的欧几里德算法 理论依据 定理1,a b Z + ?∈，1 (1)k k k k Q a P b r --=-对{1,2,...,}k n ?∈成立，其中k Q 、k P 、k r 满 足下述递推关系： 11a q b r =+，212b q r r =+，1323r q r r =+，…，111k k k k r q r r -++=+，…，110n n n r q r -+=+； 01P =，11P q =，2210P q P P =+，…，12k k k k P q P P --=+，…，12n n n n P q P P --=+； 00Q =，11Q =，2210Q q Q Q =+，…，12k k k k Q q Q Q --=+，…，12n n n n Q q Q Q --=+； {2,3,...,}k n ?∈。（课本《初等数论》第三版10P ） 显然其中(,)n r a b =且1 (1) (1)n n n n n Q a P b r --+-=，故得,s t Z ∈满 (,)sa tb a b +=。故由定理可得到求解二元一次不定方程ax by c +=的欧几里德算法 （详见课本《初等数论》第三版27P ）。下面导出求解一次同余式的欧几里德算法。 设同余式为(%)ax b m ≡，它等价于方程二元一次不定方程ax my b +=。由上面所述算法可以得到,s t Z ∈满(,)sa tm a m +=，而它等价于(,)(%)sa a m m ≡。当 (,)|a m b 时，同余式有解，一个特解为(%)(,) b x s m a m ≡ ，通解为 (%)(,)(,) b m x s k m a m a m ≡ +，{0,1,...,(,)1}k a m ?∈-。 计算过程 与求解二元一次不定方程不同的是，求解同余式不需要m 的系数k P 。 计算时可以借助表格：

欧几里德(Euclid)算法

欧几里德（Euclid ）算法 首先我们介绍整数的带余除法，它是整个数论的基础性定理之一。 定理1 （带余除法）设Z b a ∈,且0≠b ，那么存在一对整数q 和r ，使得 r bq a +=且||0b r <≤ (1) 满足以上条件的整数q 和r 是唯一确定的。 由(1)式显然有(a ,b )=(b ,r ) 我们知道，对于两个整数a 和b ，可以对其进行分解来计算它们的最大公因数，但对于大整数而言，目前还没有足够有效的办法进行。实际中常用的用来计算两个数的最大公因数的算法称为欧几里德算法。它的理论依据正是前面所述的带余除法。 欧几里德算法的数学表述如下： Z b a ∈,且0≠b ，重复应用带余除法，我们有： ???????????<<+=<<+=<<+=<<+=<<+=+++----n n n n n n n n n n n n r r r r q r r r r r q r r r r r q r r r r r q b b r r b q a 11111 12233231122121110,0,0,0,||0, 这时，0||21>>>> r r b ，由于小于|b |的正整数只有有限个以及1整除任一整数，所以这过程不能无限制地做下去，必定会出现某个n ，要么1,|1>-n n n r r r ，要么1=n r ，此时余数01=+n r 。 我们容易得到 定理2 ),(b a r n = 这是因为n n n n n r r r r r r r r b b a ======---),(),(),(),(),(112211 另外，由(1)式我们可得：

?????????<<-=<<-=<<-=<<-=---1 12232313121221110,0, 0,||0,n n n n n n r r r q r r r r r q r r r r r q b r b r b q a r 把前面的式子依次代入到后面的除式中，相应地消去1321,,,,-n r r r r ，最后， n r 可以表示为a 和b 的整系数线性组合，这时的系数即为使ax +by =(a ,b )的系数。 习题 １、什么是计算复杂性、空间复杂性？简述P 问题、NP 问题和NP －完全问题 之间的关系。 2、1. O (ax 7+3x 3+sin(x ))= 2. O (e n +an 10)= 3. O (n !+n 50)= ３、对于整数15和18，问： (1) 它们是否互素？ (2) 试用欧几里德算法求它们的最大公因子。 4、15mod 281x =-是否有解，为什么？如果有解，请给出两种计算方法。 5、求下列各数的最大公因数： (45,75), (102,222), (666,1414), (3961,952), (147,64) 并用它们的线性组合表示。 6、试证若a=bq +r , 则 gcd (a , b )=gcd (b , r ) 7、试证若(a ,b )=1,a |(bc ), 那么a |c 。 8、若d =gcd (a , b ), 则存在整数p 和q ，使得d=pa+qb 9、求下列问题的解 (1) 7mod 53≡x (2) 7mod 54≡x

解 二 元 一 次 方 程 — — — 拓 展 欧 几 里 得 算 法

二次同余方程的解 今天要讨论的问题是解方程，其中是奇质数。 证明：由费马小定理， 引理：方程有解当且仅当 定理：设满足不是模的二次剩余，即无解，那么是二次 ?剩余方程的解。 证明：由，前面的等号用二项式定理和，后面的等 ? 号用了费马小定理和是模的二次非剩余。然后 在算法实现的时候，对的选择可以随机，因为大约有一半数是模的二次非剩余，然后快速幂即可。 题目：http:--acm.timus.ru-problem.aspx?space=1num=1132 题意：求二次同余方程的解。 #include stdio.h #include stdlib.h #include string.h #include algorithm #include iostream #include math.h using namespace std; typedef long long LL; LL quick_mod(LL a, LL b, LL m)

LL ans = 1; while(b) ans = ans * a % m; a = a * a % m; return ans; --二次域乘法 T multi_er(T a, T b, LL m) ans.p = (a.p * b.p % m + a.d * b.d % m * w % m) % m; ans.d = (a.p * b.d % m + a.d * b.p % m) % m; return ans; --二次域上快速幂 T power(T a, LL b, LL m) ans.p = 1; ans.d = 0; while(b) ans = multi_er(ans, a, m); a = multi_er(a, a, m); return ans; --求勒让德符号 LL Legendre(LL a, LL p) return quick_mod(a, (p-1)1, p); LL mod(LL a, LL m)

欧几里德算法(碾转相除法)的数学证明

辗转相除法的证明 辗转相除法, 又名欧几里德算法（Euclidean algorithm ），乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。它首次出现于欧几里德的《几何原本》（第VII 卷，命题i 和ii ）中，而在中国则可以追溯至东汉出现的《九章算术》。它并不需要把二数作质因子分解。 问题重述： 证明等式()()gcd ,gcd , mod m n n m n =对每一对正整数,m n 都成立。 符号说明：函数()gcd ,m n 表示求一对正整数,m n ()m n ≥的最大公约数， mod m n 表示求m 除以n 得到的余数。 证明： 一．若m 被n 整除，此时余数0r =。易知()()gcd ,gcd ,0m n n n ==。（任意正整数和0的最大公约数是正整数本身）。 二．若m 不能被n 整除，根据条件，不妨令,m n 的最大公因数为k ，即()gcd ,m n k =。显然可分解得m ak =，n bk =，其中,a b 为正整数。 设 mod m n r =，则由定义知：m n q r ÷= (q 为商，r 为余数)。 ∴ak bk q r ÷= ，得ak bk q r =+ (1) ()r ak bk q k a bq ∴=-=- (2) 在（2）式中， ,,a b q Z +∈，∴a bq Z -∈，∴k 是r 的一个约数。 以下有反证法，证明k 是n 和r 的最大公约数。 假设k k '?≠是n 和r 的最大公约数，则k k '>。 ∴可分解得到n a k ''=，r b k ''= 由（1）式可得m n q r =+ ()m a k q b k a q b k '''''''∴=+=+ 因此k '也是m 的约数

解 二 元 一 次 方 程 — — — 拓 展 欧 几 里 得 算 法

POJ 1061 青蛙的约会（扩展欧几里得算法） 队内赛，这道题也不会，之前见过，知道用到数论知识就让sk先忽略，后来发现所有题都不怎么会，回过头来看的时候，没想到聪明的sk小同学居然会（师哥讲过我一直都没用过），然后回过头来补的时候也多亏sk 指点迷津 正题：扩展欧几里得算法 这个博客讲得很到位，讲几点自己的理解 1.扩展欧几里得算法返回值是最大公约数，在过程中改变了x，y的值，所以传参数时应该加上，而不用在意x，y的初始值 2.x，y只是 ax + by = gcd（a， b）对应的解，想要将其转换为ax1 + by1 = c 的解也很容易 x1 = （x - gcd（a， b）* c） % （b - gcd（a， b））（推导过程博客里有） 3.最后求出来的x1的值必须是非负数，并且是大于零的最优解，而x1 = （x - gcd（a， b）* c） % （b - gcd（a， b））对应的值有可能就是负数，所以保险起见 x1 = （x1 + b - gcd（a， b））?% （b - gcd（a，b）），这必定是最优解 4.（摘自百度百科） 根据欧几里得算法有 gcd(a,b) = gcd(b,a mod b); 则:ax1+ by1= bx2+ (a mod b)y2; 即:ax1+ by1= bx2+ (a - [a - b] * b)y2=ay2+ bx2- [a - b] * by2;

说明： a-[a-b]*b即为mod运算。[a-b]代表取小于a-b的最大整数。 也就是ax1+ by1 == ay2+ b(x2- [a - b] *y2); 根据恒等定理得：x1=y2; y1=x2- [a - b] *y2; 还有就是需要注意 c % gcd（a， b）不为零时方程无解 最后挂一下代码就行了吧 #includeiostream #includecstring #includecstdio #includealgorithm #includevector #includeset #includemap #includequeue #includecmath using namespace std; long long exgcd(long long a, long long b, long long x, long long y) if(b == 0) return a; long long g = exgcd(b, a % b, x, y); long long temp = x; y = temp - a - b * y;

欧几里德算法及其扩展

欧几里德与扩展欧几里德算法 欧几里德算法 欧几里德算法乂称辗转相除法，用丁计算两个整数a,b的最大公约数。 基本算法：设a=qb+r,其中a, b, q, r都是整数，贝U gcd(a,b)=gcd(b,r),即 gcd(a,b)=gcd(b,a%b)。 第一种证明： a 可以表示成a = k b + r ，贝U r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b ，而r = a - kb ，因此d|r 因此d是(b,a mod b)的公约数 假设d是(b,a mod b)的公约数，贝U d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a modb)的公约数是一样的，其最大公约数也必然相等，得 证 第二种证明： 要证欧几里德算法成立，即证：gcd(a,b)=gcd(b,r), 其中gcd是取最大公约数的意思，r=a mod b 下面证gcd (a, b) =gcd (b, r) 设 c 是a, b的最大公约数，即c=gcd (a, b),贝U有a=mc, b=nc,其中m, n为正整数，且m n五为质数 由r= a mod b 可知，r= a- qb 其中，q是正整数， 贝U r=a-qb=mc-qnc= (m-qn) c b=nc,r=(m-qn)c ,且n, (m-qn)互质(假设n, m-qn不互质，贝U n=xd, m-qn=yd 其中x,y,d都是正整数，且d>1 则 a=mc=(qx+y)dc, b=xdc,这时a,b的最大公约数变成dc,与前提矛盾, 所以

n , m-qn一定互质) 贝U gcd (b,r ) =c=gcd (a,b) 得证。 算法的实现： 最简单的方法就是应用递归算法，代码如下: 日巳 1 int gcd( int a, int b) 2 ( 3 if (b==0) 4 return a; 5 return 6 gcd(b,a%b); 7} 代码可优化如下： 1 int gcd( int a, int b) 2 ( 3 return b ? gcd(b,a%b) : a; 4 } 当然你也可以用迭代形式： 日电 1 int Gcd( int a, int b)

实现扩展欧几里德算法实验报告

实现扩展欧几里德算法实验报告 一、扩展欧几里德算法问题简介 对于不完全为0 的非负整数a，b，gcd（a，b）表示a，b 的最大公约数，必然存在整数对x，y ，使得gcd（a，b）=ax+by。 二、扩展欧几里德算法设计方法简介 欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b , d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证 三、程序代码 #include #include using namespace std; int x,y,q; void extend_Eulid(int a,int b) { if(b == 0) { x = 1;y = 0;q = a; } else { extend_Eulid(b,a%b); int temp = x; x = y; y = temp - a/b*y; } } int main()

{ int a,b; cout<<"请输入a"<>a; cout<<"请输入b"<>b; if(a < b) { int temp=a; a=b; b=temp; } extend_Eulid(a,b); printf("最大公约数=%d=(%d)*%d+(%d)*%d\n",q,x,a,y,b); return 0; } 四、算法介绍 扩展欧几里德算法是用来在已知a, b求解一组x，y使得ax+by = Gcd(a, b) =d(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。 五、实验数据 a=22 b=33 六、实验结果 七、实验体会

欧几里得算法在历史上的不同呈现

欧几里得算法在历史上的不同呈现 二国外的欧几里得算法 2.1 几何原本中的欧几里得算法 2.11 欧几里得和他的几何原本 欧几里得（Eudides 或 Eucleides，公元前三百年前后），是希腊数学家。欧几里得的《几何原本》是一部划时代的著作。 中国传统数学的最大特点是以算为中心，没有形成如同古希腊数学那样的公理化体系。《几何原本》开创了数学公理化的正确道路，促进了整个数学的发展。《几何原本》全书共由十三卷组成，第一卷到第六卷为平面几何学，它是由徐光启，利玛窦在1607年共同译完，明末传入我国，补救我国数学研究中的不足。第七卷到第十卷为数论，但与中算不同的是，全用几何方式来叙述。其中第Ⅶ卷命题Ⅰ就是用几何方式来叙述欧几里得算法。第十一卷到第十三卷为立体几何学。早在半个世纪以前，日本数学家小仓金之助把《九章算术》与《几何原本》进行比较，他认为《九章算术》是“中国的欧几里得”，作为东西方数学的代表作，《九章算术》与《几何原本》在数学发展史上的产生和流传有相似之处。欧几里得算法来源于《几何原本》，但欧几里得算法中算法思想却与古印度，日本，意大利，德国，以及我国古代现代许多数学研究一致。 2.12欧几里得算法 《几何原本》第Ⅶ卷命题Ⅰ中原文如下“设有不相等的二数，若依

次从大数中不断地减去小数，若余数总是量不尽它前面的一个数，直到最后的余数为一个单位，则该二数互素”。 命题二中“已知两个不互素的数，求它们的最大公度数。术文如下设 AB,CD是不互素的两数，求 AB,CD 的最大公度数。如果 CD 量尽AB ，那么它也能量尽它自己，那么 CD 就是CD,AB 的最大公度数。且显然CD 也是最大公度数，这是因为没有比CD大的数能量尽CD ，但是，如果CD量不尽AB，那么从AB,CD 中的较大者中不断地减去较小者，如此，将有某个余数能量尽它前面的一个。这最后的余数不是一个单位，否则AB,CD 就是互素的。” 2.2印度的不定方程组问题 一次不定分析在中国，印度，古希腊数学中多有研究，特别是对印度数学家来说是非常重要的。他们非常重视一次不定分析的研究，曾一度用它来代表这门学科。

欧几里德算法又称辗转相除法

欧几里德算法又称辗转相除法，用于计算两个整数a，b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b) 证明：a可以表示成a = kb + r，则r = a mod b 假设d是a,b的一个公约数，则有 d|a, d|b，而r = a - kb，因此d|r 因此d是(b,a mod b)的公约数 假设d 是(b,a mod b)的公约数，则 d | b ， d |r ，但是a = kb +r 因此d也是(a,b)的公约数 因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证[编辑本段] 欧几里得算法原理 Lemma 1.3.1 若a, b 且 a = bh + r, 其中h, r , 则gcd(a, b) = gcd(b, r). 证明. 假设d1 = gcd(a, b) 且d2 = gcd(b, r). 我们证明d1| d2 且d2| d 1, 因而可利用Proposition 1.1.3(2) 以及d1, d2 皆为正数得证d1 = d2. 因d1| a 且d1| b 利用Corollary 1.1.2 我们知d1| a - bh = r. 因为d1| b, d1| r 且d2 = gcd(b, r) 故由Proposition 1.2.5 知d1| d2. 另一方面, 因为d2| b 且d2| r 故d2| bh + r = a. 因此可得d2| d1. Lemma 1.3.1 告诉我们当 a > b > 0 时, 要求a, b 的最大公因数我们可以先将 a 除以 b 所得馀数若为r, 则a, b 的最大公因数等於 b 和r 的最大公因数. 因为0r < b < a, 所以当然把计算简化了. 接著我们就来看看辗转相除法. 由於gcd(a, b) = gcd(- a, b) 所以我们只要考虑a, b 都是正整数的情况. Theorem 1.3.2 (The Euclidean Algorithm) 假设a, b 且 a > b. 由除法原理我们知存在h0, r0 使得 a = bh0 + r0, 其中0r0 < b. 若r0 > 0, 则存在h1, r1 使得 b = r0h1 + r1, 其中0r1 < r0. 若r1 > 0, 则存在h2, r2 使得 r0 = r1h2 + r2, 其中0r2 < r1. 如此继续下去直到rn = 0 为止. 若n = 0 (即r0 = 0), 则gcd(a, b) = b.若n1, 则gcd(a, b) = rn - 1. 证明. 首先注意若r0 0, 由於r0 > r1 > r2 > ... 是严格递减的, 因为r0 和0 之间最多仅能插入r0 - 1 个正整数, 所以我们知道一定会有nr0 使得rn = 0. 若r0 = 0, 即 a = bh0, 故知 b 为 a 之因数, 得证 b 为a, b 的最大公因数. 若r0 > 0, 则由Lemma 1.3.1 知

g c d 欧 几 里 得 算 法

扩展欧几里得算法 扩展欧几里得算法是啥，那就要先知道什么是欧几里得算法 欧几里得算法 扩展欧几里得算法是欧几里得算法的推广，利用欧几里得算法的思想和递归求得贝祖等式a*x+b*y=gcd(a,b)不定方程中的一组x和y的解。 原理如下： 当b=0时，很显然a*x=gcd(a,b)=a，所以x=1，而y为任意数，为了同一和方便我们令y=0；当ab0时，设有两组等式a*x1+b*y1=gcd(a,b)，b*x2+(a%b)*y2=gcd(b,a%b)。根据欧几里得算法的递归思想，a和b的gcd 为t，而a=q*b+r，r=a-q*b为a，b的线性组合，又因为a%t=0，b%t=0，所以线性组合r%t=0，又有r=a%b，所以gcd(a,b)=gcd(b,a%b)。 联立等式有a*x1+b*y1=b*x2+(a%b)*y2，又有a%b=a-floor(a-b)*b[这里面floor()是向下取整的意思]， 即：ax1+by1=bx2+[a-floor(a-b)*b]*y2，我们将a，b视为未知数所以由x1*a+y1*b=y2*a+[x2-floor(a-b)*y2]*b可得 y1=[x2-floor(a-b)*y2] 这样我们就找到了扩展欧几里得的递归算法了 总结一下 欧几里得算法的递归求最大公约数是通过递归知道m=q*t+0，在下一次递归时余数r=0，递归结束，在扩展欧几里得算 法中同样是递归当b=0时递归结束，又有原理中情况1，b=0，则x=1，

y=0； void Ex_gcd(int a, int b, int x, int y) if(b == 0)--递归出口 int x1, y1; Ex_gcd(b, a%b, x1, y1); y = x1-(a-b)*y1; 上述是求得一组x0，y0解利用这个组求通解怎么求呢？ 有a(x0+n*b)+b*(y0-n*a)=gcd(a,b) 所以x=x0+n*b时n(…，-2，-1，0，1，2，…)，x就是方程的解系了，对应每一个x都应该有一个y与其相对，实际求解 时先不考虑y，当x求出时，将x带回方程求得y即可 当这里的x就包含了所有的解嘛？ 显然不是得，我们将原方程两边同除于gcd(a,b),设a1=a-gcd(a,b),b1=b-gcd(a,b) a1x+b1y=1，与原方程为同解，此时 x=x0+n*b1 又知b1=b-gcd(a,b)=b，所以这里的x比原x包含更多的解 求最小正数解 while(x0) x+=b1;求解一般线性方程 对于一般的线性方程ax+by=m，我们怎么来求解呢 首先要判断这个方程是否有解，若m%gcd(a,b)==0则方程是有解的，

欧几里得算法求乘法逆元

扩展的欧几里德算法求乘法逆元 #include /* 扩展的欧几里德算法求乘法逆元By VC++ 6.0 陈*/ int ExtendedEuclid( int f,int d ,int *result); int main() { int x,y,z; z = 0; printf("输入两个数：\n"); scanf("%d%d",&x,&y); if(ExtendedEuclid(x,y,&z)) printf("%d和%d互素，乘法的逆元是：%d\n",x,y,z); else printf("%d和%d不互素，最大公约数为：%d\n",x,y,z); return 0; } int ExtendedEuclid( int f,int d ,int *result) { int x1,x2,x3,y1,y2,y3,t1,t2,t3,q; x1 = y2 = 1; x2 = y1 = 0; x3 = ( f>=d )?f:d; y3 = ( f>=d )?d:f; while( 1 ) { if ( y3 == 0 ) { *result = x3; /* 两个数不互素则result为两个数的最大公约数，此时返回值为零*/ return 0; } if ( y3 == 1 ) { *result = y2; /* 两个数互素则resutl为其乘法逆元，此时返回值为1 */ return 1; } q = x3/y3; t1 = x1 - q*y1; t2 = x2 - q*y2; t3 = x3 - q*y3; x1 = y1;

x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; } }