数论（求逆元）

在密码学中我们经常需要用到逆元，尤其在RSA公钥密码体制中。下面简介一下求逆元的通用方法，广义欧几里得除法的逆运算。
如果a,m互素的话，那么根据欧几里得除法，最终会得到余数为1，此时我们可以消去中间变量，最终得到sa+tm=(a,m)=1，两边同时除以m可以得到sa=1(mod m)，显而易见可以得到s是a模m的逆元。
求逆元步骤就分为两部：1.判断a，m是否互素；2.根据广义欧几里得除法计算逆元，即s。
引用我们上课的PPT



通过上面的方法逐层迭代，可以求得最后的sa+tm=1，最后我们让左右两边同时模m，得到sa=1（mod m），那么根据乘法逆元的定义，可以得到s即为a模m下的逆元，即上图中a的逆元是193，下面上代码，我用的是递归的思想，自底向上进行递归

#include <iostream>
using namespace std;
int x=0,y=0;
//fun1用来判断两个数是否互素
bool fun1(int a,int m)
{
int r1,r2,r3;
if(a>m)
{
r1=a;
r2=m;
}
else
{
r1=m;
r2=a;
}
r3=-1;
while(r3!=0)
{
r3=r1%r2;
r1=r2;
r2=r3;
//	cout<<r1<<" "<<r2<<" "<<r3<<endl;
}
if(r1==1)return false;
else return true;
}
void fun2(int a,int m)
{
int r1,r2,r3;
if(a>m){r1=a;r2=m;}
else {r1=m;r2=a;}
if(r1%r2==1)
{
x=1;
y=-(r1/r2);
return;
}
//先求底层的结果，得到底层的x和y值
fun2(r2,r1%r2);
//然后迭代本层次的x和y系数值
int temp=x;
x=y;
y=temp-y*(r1/r2);
}
int main()
{
int a,m;
while(cin>>a>>m&&a!=0)
{
if(!fun1(a,m))
{
fun2(a,m);
}
else
{
cout<<"不互素"<<endl;
continue;
}
if(a>m)cout<<x<<endl;else cout<<y<<endl;
}
return 0;
}

--------------------需要详细解释的私信1124397151@qq.com---------------------------

最后

以上就是文静斑马为你收集整理的数论（求逆元）的全部内容，希望文章能够帮你解决数论（求逆元）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。