RSA
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 580 Accepted Submission(s): 432
> choose two large prime integer p, q
> calculate n = p × q, calculate F(n) = (p - 1) × (q - 1)
> choose an integer e(1 < e < F(n)), making gcd(e, F(n)) = 1, e will be the public key
> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key
You can encrypt data with this method :
C = E(m) = me mod n
When you want to decrypt data, use this method :
M = D(c) = cd mod n
Here, c is an integer ASCII value of a letter of cryptograph and m is an integer ASCII value of a letter of plain text.
Now given p, q, e and some cryptograph, your task is to "translate" the cryptograph into plain text.
101 103 7 11 7716 7746 7497 126 8486 4708 7746 623 7298 7357 3239
I-LOVE-ACM.
本题详细的介绍了RSA加密法
可以学习下
我的代码：
#include<stdio.h>
#include<string.h>
typedef __int64 ll;
ll code[100000];
ll extend_gcd(ll a,ll b,ll &x,ll &y)//扩展欧几里得算法
{
ll t,ret;
if(b==0)
{
x=1;
y=0;
return a;
}
ret=extend_gcd(b,a%b,x,y);
t=x;
x=y;
y=t-a/b*y;
return ret;
}
ll power(ll p,ll n,ll m)
{
ll sq=1;
while(n>0)
{
if(n&1)
sq=(sq%m)*(p%m)%m;
p=(p%m)*(p%m)%m;
n=n/2;
}
return sq%m;
}
int main()
{
ll p,q,e,l,phi,i,k,d,n;
ll t;
while(scanf("%I64d%I64d%I64d%I64d",&p,&q,&e,&l)!=EOF)
{
for(i=1;i<=l;i++)
scanf("%I64d",&code[i]);
phi=(p-1)*(q-1);
ll g=extend_gcd(e,phi,d,k);
n=p*q;
d=(d%phi+phi)%phi;
for(i=1;i<=l;i++)
{
t=power(code[i],d,n);
printf("%c",t);
}
printf("\n");
}
return 0;
}