欧几里得算法求逆
❶ 欧几里德算法是什么啊
欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数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)的公约数是一样的，其最大公约数也必然相等，得证。
欧几里德算法就是根据这个原理来做的，其算法用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;
}
参考资料：internet
❷ c语言，求一个数的逆的模n运算等于多少！
程序如下：
#include <conio.h>
#include <stdio.h>
int ExtEnclid(int d,int f)
{
int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;
if(d>f) d=d+f-(d=f); //交换d和f使得d<f
x1=1,x2=0,x3=f;
y1=0,y2=1,y3=d;
while(1)
{
if(y3==0)
{
return 0; //没有逆元,gcd(d,f)=x3
}
if(y3==1)
{
return y2; //逆元为y2,gcd(d,f)=1
}
k=x3/y3;
t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;
x1=y1,x2=y2,x3=y3;
y1=t1,y2=t2,y3=t3;
}
}
int main()
{
int a, n, res;
printf("求 a^(-1) mod n 的值：\n");
printf("a = ");
scanf("%d", &a);
printf("n = ");
scanf("%d", &n);
res = ExtEnclid(a,n);
if (res == 0)
{
printf("Not Exist!\n");
getch();
return (0);
}
else if(res<0)
{
res = res + n;
}
printf("a^(-1) mod n = %d\n", res);
getch();
return (0);
}
计算1/x mod n =x^(-1) mod n
就是求y，满足：
yx = 1 mod n
y是有限域F(n)上x的乘法逆元素
可用扩展的欧几里得算法求乘法逆元
扩展的欧几里德算法简单描述如下：
ExtendedEuclid(d,f)
1 （X1,X2,X3):=(1,0,f)
2 (Y1,Y2,Y3):=(0,1,d)
3 if (Y3=0) then return d'=null//无逆元
4 if (Y3=1) then return d'=Y2 //Y2为逆元
5 Q:=X3 div Y3
6 (T1,T2,T3):=(X1-Q*Y1,X2-Q*Y2,X3-Q*Y3)
7 （X1,X2,X3):=(Y1,Y2,Y3)
8 (Y1,Y2,Y3):=(T1,T2,T3)
9 goto 3
❸ 欧几里得算法是什么
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数除除数。
再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：
1、若r是a ÷ b的余数，且r不为0，则gcd(a,b) = gcd(b,r)。
⒉、a和其倍数之最大公因子为a。
另一种写法是：
⒈、令r为a/b所得余数（0≤r），若r= 0，算法结束；b即为答案。
⒉、互换：置a←b，b←r，并返回第一步。
❹ 欧几里得辗转相除法
辗转相除法， 又名欧几里德算法（Euclidean algorithm），是求最大公约数的一种方法。它的具体做法是：用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 另一种求两数的最大公约数的方法是更相减损法。辗转相除法是用来计算两个整数的最大公约数。假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然a = mc和b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 a和b的最大公约数，所以c也一定是r的最大公约数，因为r = mc - nck = (m-nk)c。
因此gcd(a,b) = gcd(b,r)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。
举例两个整数为1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此时余数为零，则21为两个数的最大公约数。
贝祖公式表明对于任意两个整数a和b，都可以找到一对可为负的整数x和y，可以使等式xa + yb = m，其中m为a和b的最大公约数，合理性稍加思考可得。如果m为1说明a和b互素。所以在互素的情况下，xa + yb = 1。这个等式对于求乘法逆元有很大的帮助。
那么如何通过贝祖公式及扩展欧几里得算法来求乘法逆元呢？举一个例子来描述什么是乘法逆元。如果ab mod m = 1，或者可以表示为ab ≡ 1 mod m，这里b就是a关于模数m的乘法逆元。计算乘法逆元的方法就是扩展欧几里得算法，以下通过一个例子来帮助理解：
假设我们要求3 关于模26的乘法逆元(隐含了3和26的最大公约数为1，即互素)。当a = 3，b = 26，则根据贝祖公式，存在整数x和y，3x + 26y = 1。
思路就是等号两边同时mod 26，等式则变成(3x + 26y) mod 26 = 1 mod 26，根据模运算的性质(a + b) mod m = (a mod m + b mod m) mod m。
所以展开等式(3x mod 26 + 26y mod 26) mod 26 = 1 mod 26。化简最终得到(3x mod 26) mod 26 = 1 mod 26。我们发现3x mod 26 = 1正好符合了乘法逆元的定义，所以欧几里得算法就是解x的关键。
下面将通过辗转相除法来求x：
第一步：26 = 3 * 8 + 2
第二步：3 = 2 * 1 + 1
统一将余数换到等号左边：
2 = 26 - 3 * 8
1 = 3 - 2 * 1
将第一行的2替换到第二行，保证等式左边永远为1，等式右边变成仅由3x + 26y组成。
1 = 3 - (26 - 3 * 8) * 1 = 3 * 9 + (-1) * 26
可得x = 9
最后9就是3关于模26的乘法逆元。它可以应用于仿射加密。
附：仿射加密的公式e(x) = ax + b mod m， 其中a与m互素， b为移动距离。
仿射解密公式d(x) = a-1(x - b) mod m
❺ 扩展欧几里得算法求逆元算法结果是负数
写一句
d=(d%MOD+MOD)%MOD;
转化成正数就可以了
❻ 急 欧几里得算法是什么原理啊
在求两个整数的最大公约数要用到欧几里得算法,简单的说就是：
设A,B(A>B)最大公约数为k,则
A = k*A1
B = k*B1
所以
C = A-B*t = k*(A1-B1*t) (C<B)
得到
(A,B) == (C,B)
欧几里德算法
欧几里德算法又称辗转相除法，用于计算两个整数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)的公约数是一样的，其最大公约数也必然相等，得证
欧几里德算法就是根据这个原理来做的，其算法用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
证明：
首先证明充分性
如果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
扩展欧几里德算法
扩展欧几里德算法不但能计算(a,b)的最大公约数，而且能计算a模b及b模a的乘法逆元，用C语言描述如下：
int gcd(int a, int b , int& ar,int & br)
{
int x1,x2,x3;
int y1,y2,y3;
int t1,t2,t3;
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;
int k;
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;
}
if( y3 == 1)
{
//有乘法逆元
ar = y2;
br = x1;
return 1;
}else{
//公约数不为1，无乘法逆元
ar = 0;
br = 0;
return y3;
}
}
扩展欧几里德算法对于最大公约数的计算和普通欧几里德算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。
首先重复拙作整除中的一个论断：
如果gcd(a,b)=d，则存在m,n，使得d = ma + nb，称呼这种关系为a、b组合整数d，m，n称为组合系数。当d=1时，有 ma + nb = 1 ，此时可以看出m是a模b的乘法逆元，n是b模a的乘法逆元。
为了证明上面的结论，我们把上述计算中xi、yi看成ti的迭代初始值，考察一组数(t1,t2,t3)，用归纳法证明：当通过扩展欧几里德算法计算后，每一行都满足a×t1 + b×t2 = t3
第一行：1 × a + 0 × b = a成立
第二行：0 × a + 1 × b = b成立
假设前k行都成立，考察第k+1行
对于k-1行和k行有
t1(k-1) t2(k-1) t3(k-1)
t1(k) t2(k) t3(k)
分别满足：
t1(k-1) × a + t2(k-1) × b = t3(k-1)
t1(k) × a + t2(k) × b = t3(k)
根据扩展欧几里德算法，假设t3(k-1) = j t3(k) + r
则：
t3(k+1) = r
t2(k+1) = t2(k-1) - j × t2(k)
t1(k+1) = t1(k-1) - j × t1(k)
则
t1(k+1) × a + t2(k+1) × b
=t1(k-1) × a - j × t1(k) × a +
t2(k-1) × b - j × t2(k) × b
= t3(k-1) - j t3(k) = r
= t3(k+1)
得证
因此，当最终t3迭代计算到1时，有t1× a + t2 × b = 1，显然，t1是a模b的乘法逆元，t2是b模a的乘法逆元。
参考资料：
http://ke..com/view/795549.htm
❼ 扩展欧几里得算法求乘法逆元1234
Q X1 X2 X3 Y1 Y2 Y31 0 4321 0 1 12343 0 1 1234 1 -3 6191 1 -3 619 -1 4 6151 -1 4 615 2 -7 4153 2 -7 4 -307 1075 31 -307 1075 2 309 -1082 14321-1082=3239
❽ 用C语言编制的求模逆元的扩展欧几里德算法，只要能基本上实现这个功能就行
扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
下面是一个使用C语言的实现：
intexGcd(inta,intb,int&x,int&y)
{
if(b==0)//当b==0时，得到解
{
x=1;y=0;
returna;
}
intr=exGcd(b,a%b,x,y);//递归调用自身，求解
intt=x;x=y;y=t-a/b*y;
returnr;
}
❾ 素数定理-欧几里得算法-乘法逆元
素数定理给出的是估计素数个数的方法：
设π(x)是小于x的素数的个数，则
π(x)≈x/lnx
eg：
64位二进制表示的素数的个数为
(1)欧拉定理
提及欧拉定理，需要先引出欧拉函数的定义：
欧拉函数Φ(n)是定义在正整数上的函数，Φ(n)的值等于序列0,1,2,3,…,n-1中与n互素的数的个数
欧拉函数的性质：
(1)m的素数时，有Φ(m)=m-1
(2)m=pq,且p和q均是素数时，有Φ(m)=Φ(p)Φ(q)=(p-1)(q-1)
(3)若m和n互素，则Φ(m×n)=Φ(m)×Φ(n)
(4)若p是一个素数，则Φ(p^e)=p^e-p^(e-1)
(5)
由欧拉函数可以延伸出欧拉定理的内容：
欧拉定理:
对于任何互素的两个整数a和n，有
1(mod n)
如果n=p是素数,则有
1(mod p)
显然欧拉定理可以看成是费马定理的推广形式。
欧拉定理可以用来简化幂的模运算
Eg：
求 的后三位数字
解： (mod 1000)的结果
有 (mod 1000)
(2)费马定理
如果p是素数，a是正整数，且gcd(a,p)=1，那么
1(mod p)
另一种形式：
如果p是素数，a是任意正整数，则对gcd(a,p)=1,有
(mod p)
(3)二次探测定理
如果p是一个素数，且0<x<p,则方程 1(mod p)的解为 x = -1、p-1。
即如果符合 1(mod p)，那么p很有可能是素数，但是仍不能肯定p就是素数。
(1)Wilson定理
对于给定的正整数n，判断n是一个素数的充要条件是 -1(mod n)。
虽然是充要条件，且Wilson的定理有很高的的理论介质。因为带有阶乘，在检测的时候计算量大，不适合检测较大素数的检测。
(2)米勒-拉宾算法
米勒-拉宾算法是一个多项式算法，能以接近概率1保证判断结果的正确性。
Miller-Rabin(n)
把n-1写成 ，其中m是一个奇数
选取随机整数a，使得
(mod n)
If (mod n)
Return (‘n是素数’)
End
For i=0到k-1
If b≡-1(mod n)
Return (‘n是素数’)
Else
b=b^2(mod n)
End
End
Return(‘n是合数’)
欧几里得算法描述：
两个整数用a，b表示，商用q表示，余数用r表示
Step1 取a，b较大者为a，较小者为b
Step2 做除法，计算并保留余数r=mod(a,b)
Step3 将原来的除数改做被除数，余数作为除数a=b,b=r
重复Step1和Step2直到r=0,返回b
乘法逆元的定义：
假设gcd(a,n)=1,则存在整数s，使得 (mod n)，即s是a(mod n)的乘法逆元素。
关于ax+by=d
设a和b是两个正整数(至少有一个非零)，d=gcd(a,b),则存在整数x和y使得ax+by=d成立，如果a、b互素，那 么存在整数x和y使得ax+by=1成立，此时可以求出ax≡1(mod b)中的x，即为逆元。
扩展欧几里得算法：
构造两个数列：
Eg：
求28mod75的乘法逆元(a=75,b=28)
gcd(28,75)=1 所以存在逆元
75=2×28+19
28=1×19+9
19=2×9+1
9=9×1+0
3×78+(-8)×28=1
所以28mod75的乘法逆元为-8
中国剩余定理完整版
Eg：
已知下列同余方程组，求解x
第一步：求M
M=2×3×5×7=210
第二步：求
第三步：求
1(mod )(i=1,2,...,k)
第四步:
(mod M)
(105×1×1+70×1×2+42×3×3+30×4×5)(mod 210)
173(mod 210)
❿ 用c语言编写扩展欧几里德算法用来求乘法逆元ab=1 mod(n) 要求我输入b，n，求出a。请编译运行通过，谢谢啦
#include <stdio.h>
int ExtendedEuclid( int f,int d ,int *result);
int main()
{
int n,b,z;
z = 0;
printf("输入两个数：\n");
scanf("%d%d",&b,&n);
if(ExtendedEuclid(n,b,&z))
printf("%d和%d互素，乘法的逆元是：%d\n",b,n,z);
else
printf("%d和%d不互素，最大公约数为：%d\n",b,n,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;
}
}
/*输入两个数：
5 14
5和14互素，乘法的逆元是：3
*/