本文共 2293 字，大约阅读时间需要 7 分钟。
Time Limit: 10 Sec Memory Limit: 512 MB Submit: 818 Solved: 480 [ ][ ][ ] Description
一种非对称加密算法的密钥生成过程如下：
1. 任选两个不同的质数 p ，q
2. 计算 N=pq , r=(p-1)(q-1)
3. 选取小于r ，且与 r 互质的整数 e
4. 计算整数 d ，使得 ed≡1 mod r
5. 二元组 (N,e) 称为公钥，二元组 (N,d) 称为私钥
当需要加密消息 n 时（假设 n 是一个小于 N 整数，因为任何格式的消息都可转为整数表示），使用公钥 (N,e)，按照
n^e≡c mod N
运算，可得到密文 c 。
对密文 c 解密时，用私钥 (N,d) ，按照
c^d≡n mod N
运算，可得到原文 n 。算法正确性证明省略。
由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。
现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。
Input
输入文件内容只有一行，为空格分隔的j个正整数e,N,c。N<=2^62,c<N
Output
输出文件内容只有一行，为空格分隔的k个整数d,n。
Sample Input
Sample Output
可以说是模拟题了
题目中第一句话：给出两个不同的质数p, q，计算N=p*q
N给你了，那么对N进行分解质因数后一定就是p*q的形式，大数分解用
之后算出r，又因为e*d=1modr，那么可以用 算出d
最后快速幂一下，两个答案就出来了
#include #include #define LL long longint cnt;LL fat[66], x1, y1;LL Abs(LL a){ if(a<0) a = -a; return a;}LL Mulit(LL a, LL b, LL mod){ LL ans = 0; a %= mod; while(b) { if(b%2) ans = (ans+a)%mod; a = a*2%mod; b /= 2; } return ans;}LL Pow(LL a, LL b, LL mod){ LL ans = 1; while(b) { if(b%2) ans = Mulit(ans, a, mod); a = Mulit(a, a, mod); b /= 2; } return ans;}LL Gcd(LL a, LL b){ if(b==0) return a; return Gcd(b, a%b);}int Miller_Rabin(LL n){ int i, j, k; LL a, x, y, mod; if(n==2) return 1; if(n<2 || n%2==0) return 0; mod = n-1, k = 0; while(mod%2==0) { mod /= 2; k++; } for(i=1;i<=11;i++) { a = rand()%(n-1)+1; x = Pow(a, mod, n); y = 0; for(j=1;j<=k;j++) { y = Mulit(x, x, n); if(y==1 && x!=1 && x!=n-1) return 0; x = y; } if(y!=1) return 0; } return 1;}LL Divi(LL n){ LL i, k, x, y, p, c; if(n==1) return 1; k = 2, p = 1; y = x = rand()%n, c = rand()%(n-1)+1; for(i=1;p==1;i++) { x = (Mulit(x, x, n)+c)%n; p = Abs(x-y); p = Gcd(n, p); if(i==k) y = x, k *= 2; } return p;}void Pollard_rho(LL n){ LL p; if(n==1) return; if(Miller_Rabin(n)) fat[++cnt] = n; else { p = Divi(n); Pollard_rho(n/p); Pollard_rho(p); }}LL ExGcd(LL a, LL b){ LL t, temp; if(b==0) { x1 = 1, y1 = 0; return a; } t = ExGcd(b, a%b); temp = x1; x1 = y1; y1 = temp-a/b*y1; return t;}int main(void){ LL e, n, c, r, d; scanf("%lld%lld%lld", &e, &n, &c); Pollard_rho(n); r = (fat[1]-1)*(fat[2]-1); d = ExGcd(e, r); d = (x1%r+r)%r; printf("%lld %lld\n", d, Pow(c, d, n)); return 0;}
转载地址：http://qmmgf.baihongyu.com/