【BZOJ-4522】密钥破解 数论 + 模拟 （ Pollard_Rho分解 + Exgcd求逆元 + 快速幂 + 快速乘）

时间：2022-02-17 10:43:06

4522: [Cqoi2016]密钥破解

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

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<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<cstdlib>

using namespace std;

long long read()

{

    long long x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; 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=;

    for (long long i=y; i; i>>=,x=(x+x)%p)

        if (i&) re=(re+x)%p;

    return re;

}

long long Quick_Pow(long long x,long long y,long long p)

{

    long long re=;

    for (long long i=y; i; i>>=,x=Quick_Mul(x,x,p))

        if (i&) re=Quick_Mul(re,x,p);

    return re;

}

void Exgcd(long long a,long long b,long long &x,long long &y)

{

    if (b==) {x=; y=; 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==) return a;

    return Gcd(b,a%b);

}

#define T 10007

long long Pollard_Rho(long long n)

{

    long long x,y,cnt=,k=;

    x=rand()%(n-)+; y=x;

    while ()

        {

            cnt++;

            x=(Quick_Mul(x,x,n)+T)%n;

            long long gcd=Gcd(abs(x-y),n);

            if (<gcd && gcd<n) return gcd;

            if (x==y) return n;

            if (cnt==k) y=x,k<<=;

        }

}

int main()

{

    srand(T);

    e=read(),N=read(),c=read();

    P=Pollard_Rho(N); Q=N/P;

    r=(P-)*(Q-);

    long long Inv=GetInv(e,r);

    printf("%lld %lld",Inv,Quick_Pow(c,Inv,N));

    return ;

}

WA了好几次,发现是复制的时候少复制了一个头文件.....(不是应该CE的说么??)

相关文章