扩展欧几里得求逆元
用扩展欧几里得求解逆元是一种常用的方法,当然还有其他的方法。这里主要介绍两种,一种就是扩展欧几里得,另一种是不常用的方法。到后面会介绍。
你是否经常遇到过类似的问题
(A/B)%Mod。此时,要先计算B%Mod的逆元p, 其实他是用逆元解决的典型题目。但是在使用逆元时候你需满足一下两个条件才能保证得到正确的结果。
一、gcd(B,Mod) == 1,显然素数肯定是有逆元的。
二、这里B需要是A的因子
下面就给出扩展欧几里得的典型式子:a*x + b*y =1 求得x即为a%b的逆元; y即为b%a的逆元。
另一种方法是:p = b^(Mod-2) % Mod,因为b^(Mod-1)%Mod = 1(这里需要Mod为素数),因为这种方法不常用,因此这里不再详细介绍。
下面就给出求解逆元的模版(代码非原创)
扩展欧几里德求逆元模板:
#include<iostream>
#define __int64 long long
using namespace std;
//举例 3x+4y=1 ax+by=1
//得到一组解x0=-1,y0=1 通解为x=-1+4k,y=1-3k
inline __int64 extend_gcd(__int64 a,__int64 b,__int64 &x,__int64 &y)//ax+by=1返回a,b的gcd,同时求的一组满足题目的最小正整数解
{
__int64 ans,t;
if(b==0){x=1;y=0;return a;}
ans=extend_gcd(b,a%b,x,y);t=x;x=y;y=t-(a/b)*y;
return ans;
}
//(a/b)%mod=c 逆元为p,(p*b)%mod=1
//(a/b)*(p*b)%mod=c*1%mod=c
// (p*b)%mod=1 等价于 p*b-(p*b)/mod*mod=1其中要求p,b已知 等价于 ax+by=1
//其中x=p(x就是逆元),y=p/mod,a=b,b=b*mod 那么调用extend_gcd(b,b*mod,x,y)即可求(a/b)%mod的逆元等价于a*p%mod
int main()
{
__int64 a,b,x,y,c,gcd,mod,p;//ax+by=c
while(cin>>a>>b>>c)
{
gcd=extend_gcd(a,b,x,y);
cout<<x<<" "<<y<<endl;
if(c%gcd){cout<<"无解!"<<endl;continue;}
cout<<"x="<<x*c/gcd<<" y="<<y*c/gcd<<endl;
}
return 0;
}
void extend_Euclid(int a, int b)
{
if(b==0)
{
x = 1;
y = 0;
return;
}
extend_Euclid(b, a%b);
int t = x;
x = y;
y = t - a/b*y;
}
int main()
{
//b%mod的逆元
int b,mod;
while(cin>>b>>mod){
// x=0;y=0;
extend_Euclid(b,mod);
cout<<(x%mod+mod)%mod<<endl;
}
return 0;
}
分享到:
相关推荐
扩展欧几里得算法求逆元
密码学考试复习(关于快速指数算法和扩展欧几里得求逆元),之前考试自己整理的,今天又要学了。里面的算法还能看,还整理的比较透彻当时。备用了留在这。不知道为什么之前上传的xmind一点就跳转到别的页面了,这次...
欧几里得是数论中的一个最初步的概念,它用来判断两个数的最大公因子,扩展的欧几里得能够进一步实现在两个数互素情况下的乘法可逆元。求可逆元是一些算法的基础。
此为扩展欧几里得算法求乘法逆元的完整程序,图形界面,使用 vc6.0 完成,完全标准正式的格式,绝对值10积分,有完整的代码,请使用 vc6.0 打开 DSW 工程文件,然后就可完全执行。
扩展欧几里得求逆-扩展欧几里得算法求乘法逆元
matlab的M函数文件,附带了函数的使用说明了
用递归实现的求逆元的代码,使用中的算法是扩展的欧几里得算法。输入本元和模数,得到乘法逆元。
加密解密的基础,扩展欧几里得算法(辗转相除法)
介绍了扩展欧几里得算法的实现代码,有需要的朋友可以参考一下
RSA编码实现,创建公钥和私钥,并判定生成的是否是素数,生成界面和菜单便于用户选择,用扩展欧几里得短发求乘法逆元,快速模幂算法,
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
此文档是拓展欧几里得的ppt,里面还囊括了费马小定理,逆元,欧拉降幂相关的,可谓应有尽有
根据扩展欧几里得算法实现了对输入的一个数字求取乘法逆元。
扩展Euclidean算法求乘法逆原理详解与算法实现工程文件 详解博客地址:https://blog.csdn.net/m0_52316372/article/details/125687627
第八章 离散对数问题两种算法的测由于源代码中有互素判断,扩展欧几里得算法求逆元和多余随机策略代码,显得有点多和乱,Shanks法和pollards Rho部分代
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发
信息安全工程RSA算法实验,使用Java的大整数实现快速模指数算法、欧几里得算法、扩展欧几里得算法、求逆元算法、产生公钥和私钥、以及分组加密与解密,支持中文、英文和特殊字符,支持自定义密钥长度。可直接运行。
2.利用所学的编程语言,以及扩展欧几里得欧拉定理实现求模的逆元 2. 输入要求逆元的数,以及模的数字 3. 输出该数模下的逆元 2.兴趣对学习的帮助是极大的,很
使用这个可以在window系统的python3.8中引用gmpy2,这个可以快速计算a mod n 的逆元,无需使用扩展欧几里得算法