4522: [Cqoi2016]密钥破解
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 290 Solved: 148[][][]Description
一种非对称加密算法的密钥生成过程如下：
1.任选两个不同的质数p,q
2.计算N=pq,r=(p−1)(q−1)
3.选取小于r，且与r互质的整数e
4.计算整数d，使得ed≡1KQ/r
5.二元组(N,e)称为公钥，二元组(N,d)称为私钥
当需要加密消息M时（假设M是一个小于L整数，因为任何格式的消息都可转为整数表示），
使用公钥(N,e)，按照n^e≡cKQ/N运算，可得到密文C。
对密文C解密时，用私钥(N,d)，按照c^d≡nKQ/N运算，可得到原文M。算法正确性证明省略。
由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。
通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的
人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。
现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。
Input
输入文件内容只有一行，为空格分隔的j个正整数e,N,c。N<=2^62,c<N
Output
输出文件内容只有一行，为空格分隔的k个整数d,n。
Sample Input
3 187 45
Sample Output
107 12 //样例中 p = 11, q = 17
HINT
Source
Solution
跟着题意模拟...数论大集合(和 猪文 比好像还差点?)
先用Pollard_Rho分解$N$,求出$r$,答案为$Inv(e,r)$和$c^{Inv(e,r)}%N$
求逆元的过程,ExGcd解决好了.分解就是各种随,挺高效的...
坑点:需要快速乘,不然乘法爆longlong....
Code
#include#include #include #include #include #include using namespace std;long long read(){ long long x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}long long e,N,c,r,P,Q;long long Quick_Mul(long long x,long long y,long long p){ long long re=0; for (long long i=y; i; i>>=1,x=(x+x)%p) if (i&1) re=(re+x)%p; return re;}long long Quick_Pow(long long x,long long y,long long p){ long long re=1; for (long long i=y; i; i>>=1,x=Quick_Mul(x,x,p)) if (i&1) re=Quick_Mul(re,x,p); return re;}void Exgcd(long long a,long long b,long long &x,long long &y){ if (b==0) {x=1; y=0; return;} Exgcd(b,a%b,y,x); y-=(a/b)*x;}long long GetInv(long long n,long long p){ long long x,y; Exgcd(n,p,x,y); return (x%p+p)%p;}long long Gcd(long long a,long long b){ if (b==0) return a; return Gcd(b,a%b);}#define T 10007long long Pollard_Rho(long long n){ long long x,y,cnt=1,k=2; x=rand()%(n-1)+1; y=x; while (1) { cnt++; x=(Quick_Mul(x,x,n)+T)%n; long long gcd=Gcd(abs(x-y),n); if (1
WA了好几次,发现是复制的时候少复制了一个头文件.....(不是应该CE的说么??)