4522: [Cqoi2016]密鑰破解

Time Limit:?10 Sec??Memory Limit:?512 MB
Submit:?290??Solved:?148
[Submit][Status][Discuss]

Description

一種非對(duì)稱(chēng)加密算法的密鑰生成過(guò)程如下： 1.任選兩個(gè)不同的質(zhì)數(shù)p,q 2.計(jì)算N=pq,r=(p?1)(q?1) 3.選取小于r，且與r互質(zhì)的整數(shù)e 4.計(jì)算整數(shù)d，使得ed≡1KQ/r 5.二元組(N,e)稱(chēng)為公鑰，二元組(N,d)稱(chēng)為私鑰 當(dāng)需要加密消息M時(shí)（假設(shè)M是一個(gè)小于L整數(shù)，因?yàn)槿魏胃袷降南⒍伎赊D(zhuǎn)為整數(shù)表示）， 使用公鑰(N,e)，按照n^e≡cKQ/N運(yùn)算，可得到密文C。 對(duì)密文C解密時(shí)，用私鑰(N,d)，按照c^d≡nKQ/N運(yùn)算，可得到原文M。算法正確性證明省略。 由于用公鑰加密的密文僅能用對(duì)應(yīng)的私鑰解密，而不能用公鑰解密，因此稱(chēng)為非對(duì)稱(chēng)加密算法。 通常情況下，公鑰由消息的接收方公開(kāi)，而私鑰由消息的接收方自己持有。這樣任何發(fā)送消息的 人都可以用公鑰對(duì)消息加密，而只有消息的接收方自己能夠解密消息。 現(xiàn)在，你的任務(wù)是尋找一種可行的方法來(lái)破解這種加密算法，即根據(jù)公鑰破解出私鑰，并據(jù)此解密密文。

Input

輸入文件內(nèi)容只有一行，為空格分隔的j個(gè)正整數(shù)e,N,c。N<=2^62,c<N

Output

輸出文件內(nèi)容只有一行，為空格分隔的k個(gè)整數(shù)d,n。

Sample Input

3 187 45

Sample Output

107 12
//樣例中 p = 11, q = 17

HINT

Source

Solution

跟著題意模擬...數(shù)論大集合(和 豬文 比好像還差點(diǎn)?)

先用Pollard_Rho分解$N$,求出$r$,答案為$Inv(e,r)$和$c^{Inv(e,r)}%N$

求逆元的過(guò)程,ExGcd解決好了.分解就是各種隨,挺高效的...

坑點(diǎn):需要快速乘,不然乘法爆longlong....

Code

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<cstdlib> 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 10007 long 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<gcd && gcd<n) return gcd;if (x==y) return n;if (cnt==k) y=x,k<<=1;} } int main() {srand(T);e=read(),N=read(),c=read();P=Pollard_Rho(N); Q=N/P;r=(P-1)*(Q-1);long long Inv=GetInv(e,r);printf("%lld %lld",Inv,Quick_Pow(c,Inv,N));return 0; }

WA了好幾次,發(fā)現(xiàn)是復(fù)制的時(shí)候少?gòu)?fù)制了一個(gè)頭文件.....(不是應(yīng)該CE的說(shuō)么??)

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5467128.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ-4522】密钥破解 数论 + 模拟 （ Pollard_Rho分解 + Exgcd求逆元 + 快速幂 + 快速乘）...的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。