本文主要是介绍【HDU】 1211 RSA,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
RSA
题目链接
- RSA
题目大意
题目扯了一堆没用的,最后给了两个式子
de≡1(mod F(n))
M=cd mod n
现在给出e,F(n),以及c和n,让你求M,用%c输出。
题解
好像上面已经讲完了…先扩欧求d,然后快速幂求m。
代码
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#define LL long longusing namespace std;LL p,q,e,l,a,d,c;LL extend_gcd(LL a,LL b,LL &x,LL &y)
{LL ans;if (b==0){x=1; y=0;return a;}else ans=extend_gcd(b,a%b,x,y);LL t=x;x=y;y=t-(a/b)*y;return ans;
}LL qmi(LL a,LL b,LL mod)
{LL ans=1;while (b){if (b&1) ans=(a*ans)%mod;b=b>>1;a=(a*a)%mod;}return ans;
}int main()
{while(scanf("%I64d%I64d%I64d%I64d",&p,&q,&e,&l)!=EOF){LL f=(q-1)*(p-1),n=p*q;extend_gcd(e,f,d,c);while (d<0) d+=f;for (int i=0;i<l;i++){scanf("%I64d",&a);LL ans=qmi(a,d,n);printf("%c",ans);}printf("\n");}return 0;
}
这篇关于【HDU】 1211 RSA的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!