POJ 2447 RSA 解公钥密码 - c++编程基础

点击打开链接 RSA

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 3415		Accepted: 729

Description

RSA is the best-known public key encryption algorithm. In this algorithm each participant has a private key that is shared with no one else and a public key which is published so everyone knows it. To send a secure message to this participant, you encrypt the message using the widely known public key; the participant then decrypts the messages using his or her private key. Here is the procedure of RSA:

First, choose two different large prime numbers P and Q, and multiply them to get N (= P * Q).
Second, select a positive integer E (0 < E < N) as the encryption key such that E and T= (P - 1) * (Q - 1) are relatively prime.
Third, compute the decryption key D such that 0 <= D < T and (E * D) mod T = 1. Here D is a multiplicative inverse of E, modulo T.

Now the public key is constructed by the pair {E, N}, and the private key is {D, N}. P and Q can be discarded.

Encryption is defined by C = (M ^ E) mod N, and decryption is defined by M = (C ^ D) mod N, here M, which is a non-negative integer and smaller than N, is the plaintext message and C is the resulting ciphertext.

To illustrate this idea, let’s see the following example:
We choose P = 37, Q = 23, So N = P * Q = 851, and T = 792. If we choose E = 5, D will be 317 ((5 * 317) mod 792 = 1). So the public key is {5, 851}, and the private key is {317, 851}. For a given plaintext M = 7, we can get the ciphertext C = (7 ^ 5) mod 851 = 638.

As we have known,for properly choosen very large P and Q, it will take thousands of years to break a key, but for small ones, it is another matter.

Now you are given the ciphertext C and public key {E, N}, can you find the plaintext M

Input

The input will contain several test cases. Each test case contains three positive integers C, E, N (0 < C < N, 0 < E < N, 0 < N < 2 ^ 62).

Output

Output the plaintext M in a single line.

Sample Input

638 5 851

Sample Output

Source

POJ Monthly,static
要求明文M，根据公式M=C^D(MOD N),题目给你C和N了，所以只要求出D来就可以了，而(E*D)mod T=1,E已知，因此只要求出T来，D就知道了，而T=(P-1)*(Q-1),知道P,Q就能求T，又已知N=P*Q，N已知，因此对N做大数分解，就得到素因子，逐步往回返就能求出最终答案。

//376K	375MS
#include
  
   
#include
   
     #include
    
      #include
     
       #define Times 11 #define inf ((long long)1<<61) #define C 201 long long c,e,n; long long jl[501],mini=inf;//jl里面存的是大数的所有质因子，mini为最小的质因数 int ct; long long gcd(long long a,long long b)//最大公约数 { return b==0 a:gcd(b,a%b); } long long random(long long n)//生成随机数 { return (long long)((double)rand()/RAND_MAX*n+0.5); } long long multi(long long a,long long b,long long m)//a*b%m { long long ret=0; while(b>0) { if(b&1)ret=(ret+a)%m; b>>=1; a=(a<<1)%m; } return ret; } long long quick_mod(long long a,long long b,long long m)//a^b%m { long long ans=1; a%=m; while(b) { if(b&1) { ans=multi(ans,a,m); b--; } b/=2; a=multi(a,a,m); } return ans; } long long pollard_rho(long long n)//整数n分解,c一般为201 { long long x,y,d,i=1,k=2; x=random(n-1)+1; y=x; while(1) { i++; x=(multi(x,x,n)+c)%n; d=gcd(y-x,n); if(1