逆元

逆元的解释

为什么会有逆元这个概念。

因为 有时我们需要计算 (A/B) % M 的值， 如果B过大，或者A过大，可能会爆精度，然后我们就想到能不（A%M / B%M）

发现这种方法不对，那我们可以将除法换成乘法(A *B^-1)% M 这样就能转化成 (A % M *B^-1% M)% M

所以我们就要来求B^{-1的值，因为不能用分数，所以我们就设定B}-1为B的逆元

先设C为B的逆元，由上面可以知道由(a/b)%M，可以推出B*C=1(mod m)

则(A/B)%m = (A/B)*1%m = (A/B)*(B*C%M)%M= A*C(mod M)

即A/B的模等于A*B的逆元

还有一种更接地气的解释在此记录一下，首先我们设定一个加法取模的世界，是一个以0为中心的世界，有一个点从世界的中心加了3，然后又加了一个数使得点回到了世界中心，这个数就是逆元

然后又是一个乘法取模且中心为1的世界，有一个点从中心*3mod7，然后又突然乘了一个数让点mod7回到了世界中心，这个数就是在乘法世界mod7的逆元，这个世界没有除法，没有分数，因为3*5mod7=1，所以3mod7的一个逆元就是5，所以5和3就是在mod7的条件下互为逆元

为什么要逆元呢，因为除法是定义内会出现不可计算的情况，比如说3/5mod7，在这个世界里就变成了3*3mod7这就可以推导出公式(A/B)%p=(A*B^-1)%p=(A%p*B-1%p)%p ==> 推导之后变成了(3/5)mod7=((3mod7)*(5^-1))mod7=((3mod7)*(3mod7))mod7

对于求逆元就要求B*C=1(mod m)里C的值，首先这个方程可以写成B*C+k*m=1(k为任意整数)，这样我们就可以使用拓展欧几里得来求

拓展欧几里得的推导(理解难度比较高，闲麻烦的也可以背代码)： 对于这个我们其实就是利用辗转相除法，我们可以知道，我们辗转相除法的边界是a=d，b=0，（a和b为要求最大公约数的两个数，d为他们的公约数），此时我们可以知道a就是最大公约数，我们还可以知道，在这时，一定有个解是x=1，y=0，即a * 1+b * 0 =d，（a此时等于d，b等于0）。这个有什么用呢？
我们知道gcd（a，b）=gcd（b，a%b），如果我们可以推导出每一次的解x和y，与相除后的解x1和y1的关系我们就可以算出其中的一个接了，（x和y相当于是a和b的解，x1和y1是a已经变成了b，b变成了a%b时的解），我们下面推导一下，x、y和x1、y1之间有什么关系

这样我们就可以得到x、y和x1、y1之间的关系了，所以我们只要在回溯的时候计算一下就好了。

2019蓝桥杯CA RSA解密

看题目我们就可以看出来，这一题有点难，首先我们获得的是n，因为n是由质数q和p相乘所得到的，那么我们就可以通过枚举来暴力的到q和p的值，这时候我们注意d*e/(p-1)(q-1)的余数为1，那么我们就先设s=(p-1)(q-1)，推到出一个方程d*e=1%s，这就和我们上面说到的逆元方程一样，那么我们就可以转化为求d的逆元e，其中d题目给出了而s我们计算出来了，这样我们代入拓展欧几里得就可以求出我们需要的逆元e，然后再通过快速幂，快速乘（快速幂的乘法会越界，所以需要快速乘）求的X=C^e mod n。具体代码如下

#include<iostream>
using namespace std;
typedef long long ll;
ll q,p,e,x,y,s;
ll n=1001733993063167141;
ll d=212353;
ll c=20190324;
//枚举得到q和p
void init(){
	for(ll i=2;i<n;i++){
		if(n%i==0){
			q=i;p=n/i;
			s=(q-1)*(p-1);
			return;
		}
	}
}
//拓展欧几里得代码，理解完上面步骤的结果
void ex_gcd(ll a,ll b){
	if(b==0){
		x=1;
		y=0;
		return;
	}
	ex_gcd(b,a%b);
	ll k=x; //因为x会变化所以先记录x
	x=y;    //x和y在上面已经定义完成
	y=k-(a/b)*y;
}
//快速乘（没什么好讲的）
ll mul(ll a,ll b,ll mod){
	ll ans=0;
	while(b){
		if(b&1){
			ans=(ans+a)%mod;
		}
		a=(a*2)%mod;
		b>>=1;
	}
	return ans;
}
//快速幂（也没什么好讲的）
ll power(ll a,ll b,ll mod){
	ll ans=1;
	while(b){
		if(b&1){
			ans=mul(ans,a,mod);
		}
		a=mul(a,a,mod)%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	//init();  
	//ex_gcd(d,s);  求出初始逆元
	//e=(x+s)%s;    有可能逆元为负数，那就需要将其改正
	//num=power(c,e,n); 求出X的值
	cout<<"579706994112328949"<<endl; //因为正常的提交会导致超时，且这一题为填空题，所以只需要提交答案
	return 0;
}
r(c,e,n); 求出X的值
	cout<<"579706994112328949"<<endl; //因为正常的提交会导致超时，且这一题为填空题，所以只需要提交答案
	return 0;
}

最后

以上就是调皮砖头为你收集整理的RSA解密（逆元，快速幂，快速乘）逆元的全部内容，希望文章能够帮你解决RSA解密（逆元，快速幂，快速乘）逆元所遇到的程序开发问题。

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