RSA

RSA is one of the most powerful methods to encrypt data. The RSA algorithm is described as follow:

> 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) = m ^e  mod n

When you want to decrypt data, use this method :

M = D(c) = c ^d  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.

Each case will begin with four integers p, q, e, l followed by a line of cryptograph. The integers p, q, e, l will be in the range of 32-bit integer. The cryptograph consists of l integers separated by blanks.  

For each case, output the plain text in a single line. You may assume that the correct result of plain text are visual ASCII letters, you should output them as visualable letters with no blank between them.

JGShining（极光炫影）

杭电ACM省赛集训队选拔赛之热身赛

Eddy

 

 

 

 

这个题目的真的是相当水，我本来一开始正在发愁又要解线性同余方程了，可是当我看到别人的博客此题数据极

 

弱，让我颇有点不太适应的，我顿时觉得还是poj的数论题目的比较刺激啊，唉，Romancehowever, is rockythis

 

month!!!!感情不顺，只好做数论题目让我开心点！！！

 

n=p*q,      f(n)=(p-1)*(q-1),       d*e%f(n)=1, m=c^d%n,我们竟然按照这个式子模拟就能过了！！！！

 

让我等屌丝惊呆了！！！！！！！！！！！！！！！

 

 

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int i,j,p,q,f,e,l,c,m,n,d;
    while(scanf("%d%d%d%d",&p,&q,&e,&l)!=EOF)
    {

      n=p*q;
      f=(p-1)*(q-1);
      d=1;
      while(d*e%f!=1)
      d++;
      for(i=0;i<l;i++)
      {
          scanf("%d",&c);
          int t=1;
          for(j=0;j<d;j++)
          {
              t=(t*c)%n;
          }
          printf("%c",t);
      }
      cout<<endl;
    }
    return 0;
}