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));
}