`
- 浏览:
11343767 次
-
#include <stdio.h>
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;
}
}
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
用递归实现的求逆元的代码,使用中的算法是扩展的欧几里得算法。输入本元和模数,得到乘法逆元。
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
RSA加密算法,主要包括Miller_Rabin概率检测法、扩展欧几里德算法求乘法逆元、指数求余运算,Powermod算法、密钥的产生以及整个加密、解密过程。
%A为矩阵,n为A的秩,q为大素数,内含两个函数,invmodgaoshi.m求矩阵的模逆矩阵,Eulid.m求元素modq的乘法逆元,invmodgaoshi.m会自动调用Eulid.m。使用时调用invmodgaoshi.m传入参数,就可使用,含参数使用注释。
5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性方程(同余方程) 7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler Function欧拉函数 9. Farey总数 9. Farey序列构造 10. ...
因为key_D和key_Z互素,根据欧几里德算法,GCD(key_D,key_Z) = 1,而扩展欧几里德算法key_D存在模key_Z乘法逆元的充分必要条件是GCD(key_D,key_Z) = 1。至于key_E怎么得到,用辗转相除法即可得到,下面还会就模key...
因为key_D和key_Z互素,根据欧几里德算法,GCD(key_D,key_Z) = 1,而扩展欧几里德算法key_D存在模key_Z乘法逆元的充分必要条件是GCD(key_D,key_Z) = 1。至于key_E怎么得到,用辗转相除法即可得到,下面还会就模key...
5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性方程(同余方程) 7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler Function欧拉函数 9. Farey总数 9. Farey序列构造 10. ...