LibreOJ 2045 「CQOI2016」密钥破解

发表于 | 分类于 |

嗯，一看就是个裸题，然鹅还是 RE 了……
看来不能过度信任 Pollard-Rho 的正确率。

由于这题保证了 \(N\) 是两个质数的乘积，所以其实 Pollard-Rho 只要找个因子就好了，不用 Miller-Rabin 判断。
不过我的睿智做法是先用 \(10^7\) 以内的数枚举它的因子判定，然后再 Pollard-Rho。

然后扩欧一波就没了。

代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long N,r,e,c,d;
vector<long long> p;
inline long long fmul(long long a,long long b,long long mod)
{
    return (a * b - (long long)((long double)a / mod * b) * mod + mod) % mod;
}
inline long long fpow(long long a,long long b,long long mod)
{
    long long ret = 1;
    for(;b;b >>= 1)
        (b & 1) && (ret = fmul(ret,a,mod)),a = fmul(a,a,mod);
    return ret;
}
inline bool witness(long long x,long long p)
{
    if(fpow(x,p - 1,p) ^ 1)
        return 0;
    long long k = p - 1;
    while(!(k & 1))
    {
        k >>= 1;
        long long t = fpow(x,k,p);
        if((t ^ 1) && (t ^ p - 1))
            return 0;
        if(t == p - 1)
            return 1;
    }
    return 1;
}
inline bool Miller_Rabin(long long n)
{
    if(n == 1)
        return 0;
    const int base[] = {2,3,7,61,24251,19260817};
    for(register int i = 0;i < 6;++i)
        if(n == base[i])
            return 1;
        else if(!witness(base[i],n))
            return 0;
    return 1;
}
void Pollard_Rho(long long n)
{
    if(Miller_Rabin(n))
    {
        p.push_back(n);
        return ;
    }
    const long long c = 1e9 + 9;
    const int k = 200;
    long long t1 = 1e9 + 7;
    long long t2 = (fmul(t1,t1,n) + c) % n;
    long long p = 1;
    int i = 0;
    while(t1 ^ t2)
    {
        ++i,p = fmul(p,abs(t1 - t2),n);
        if(!p)
        {
            long long d = __gcd(abs(t1 - t2),n);
            Pollard_Rho(d),Pollard_Rho(n / d);
            return ;
        }
        if(!(i % k))
        {
            long long d = __gcd(p,n);
            p = 1;
            if((d ^ 1) && (d ^ n))
            {
                Pollard_Rho(d),Pollard_Rho(n / d);
                return ;
            }
        }
        t1 = (fmul(t1,t1,n) + c) % n,t2 = (fmul(t2,t2,n) + c) % n,t2 = (fmul(t2,t2,n) + c) % n;
    }
    long long d = __gcd(p,n);
    if((d ^ 1) && (d ^ n))
        Pollard_Rho(d),Pollard_Rho(n / d);
}
inline void exgcd(long long a,long long b,long long &x,long long &y)
{
    if(!b)
    {
        x = 1,y = 0;
        return ;
    }
    exgcd(b,a % b,y,x);
    y = (y - fmul(a / b,x,r) + r) % r;
}
int main()
{
    scanf("%lld%lld%lld",&e,&N,&c);
    long long T = N;
    for(register long long i = 1;i * i <= T && i <= 1e7;++i)
        if(!(T % i) && Miller_Rabin(i))
            T /= i,p.push_back(i);
    Pollard_Rho(T);
    r = (p[0] - 1) * (p[1] - 1);
    long long temp;
    exgcd(e,r,d,temp);
    printf("%lld %lld\n",d,fpow(c,d,N));
}