Hust oj 1953 RSA验证（快速幂）_综合

RSA验证

Time Limit: 1000 MS

Memory Limit: 32768 K

Total Submit: 38(24 users)

Total Accepted: 27(23 users)

Rating:

Special Judge: No

Description

RSA算法是一种非对称加密算法，由公钥和密钥两部分组成。公钥：P=(e,n)；密钥：S=(d,n)。
RSA的密钥和公钥生成过程是：
1.取两个随机大素数p和q，使p≠q。
2.计算n=pq。
3.选取一个与f(n)互质的小奇数e，其中f(n)=(p-1)(q-1)。
4.对模f(n)，计算e的乘法逆元d的值。
5.将对P=(e,n)公开，作为公钥。
6.将对S=(d,n)保密，作为密钥。
所以对于消息M，计算：P(M)=M^e mod n，得到密文C。
对于密文C，计算：S(C)=M^d mod n，得到明文M。
当你了解了加密和解密的过程之后就可以判断一个加密过的信息，是不是你给出的公钥加密过的。

Input

每组数据有六行。每行分别包含整数p，q，e，d，C，M。当p=q=e=d=C=M=0时，输入结束。

输入数据保证所有的数都在64位整数的范围内。

Output

你需要输出该密文是否为给定的消息M经过P加密过的。如果是，请输出“Yes”并换行；如果不是，请输出该消息通过加密后的正确的密文。

Sample Input

11 29 3 187 254 100

1277 1493 131 1351547 947015 400

0 0 0 0 0 0

Sample Output

Yes

947005

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;typedef long long LL;
LL p,q,e,d,c,n,m;LL PowerMod(LL a,LL b,LL c)
{LL ans = 1;a %= c;while(b > 0){if(b % 2 == 1)ans = (ans * a) % c;b /= 2;a = (a * a) % c;}return ans;
}int main()
{while(~scanf("%lld%lld%lld%lld%lld%lld",&p,&q,&e,&d,&c,&m) && (p+q+e+d+c+m)){n = p * q;LL re = PowerMod(m,e,n);if(re == c)printf("Yes\n");elseprintf("%lld\n",re);}
}