`
java-mans
  • 浏览: 11343767 次
文章分类
社区版块
存档分类
最新评论

扩展欧几里德算法求乘法逆元(C语言版)

 
阅读更多
#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;
  }
  }
分享到:
评论

相关推荐

    扩展的欧几里得算法(实现求乘法逆元)

    欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。

    CPP求逆元代码 扩展欧几里得

    用递归实现的求逆元的代码,使用中的算法是扩展的欧几里得算法。输入本元和模数,得到乘法逆元。

    Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m

    Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。

    欧几里德乘法逆元算法实现

    乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发

    欧几里德算法和扩展欧几里德算法

    欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。

    RSA加密算法

    RSA加密算法,主要包括Miller_Rabin概率检测法、扩展欧几里德算法求乘法逆元、指数求余运算,Powermod算法、密钥的产生以及整个加密、解密过程。

    Matlab高斯消元法求高价矩阵模q下逆矩阵函数,包含invmodgaoshi.m和Eulid.m.rar

    %A为矩阵,n为A的秩,q为大素数,内含两个函数,invmodgaoshi.m求矩阵的模逆矩阵,Eulid.m求元素modq的乘法逆元,invmodgaoshi.m会自动调用Eulid.m。使用时调用invmodgaoshi.m传入参数,就可使用,含参数使用注释。

    ACM 算法模板集

    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...

    计算机网络课程设计:RSA加密解密

    因为key_D和key_Z互素,根据欧几里德算法,GCD(key_D,key_Z) = 1,而扩展欧几里德算法key_D存在模key_Z乘法逆元的充分必要条件是GCD(key_D,key_Z) = 1。至于key_E怎么得到,用辗转相除法即可得到,下面还会就模key...

    上海交通大学ACM算法模板

    5. Extended Euclid扩展欧几里德算法 6. Modular Linear Equation模线性方程(同余方程) 7. Chinese Remainder Theorem中国余数定理(互素于非互素) 8. Euler Function欧拉函数 9. Farey总数 9. Farey序列构造 10. ...

Global site tag (gtag.js) - Google Analytics