OI - 密钥破解(POJ)

一道练习题,毕竟学了 Miller_Rabin 和 Pollard_Rho 还是得运用一下 ~


Part1. 题意(简化版)

传送门 - LOJ

Part1/1. 题面

给出正整数 $N,e,c$ 。其中 $N=p\times q$,$p,q$ 均为质数。
正整数 $r=(p-1)(q-1)$,保证 $r$ 与 $e$ 互质,且存在正整数 $d$ 使得 $e\times d\equiv1\pmod r$。

求出 $d$,并输出 $c^d\bmod N$。

Part1/2. 数据规模

$1\leq N,e,c\leq 2^{62}$。


Part2. 解析

既然简化的题意都说得这么直白了,也没有必要纠结要怎么求解了 awa(然而比赛时,你需要的就是把题目变成这样一些计算步骤)

首先要根据 $N$ 求出 $p,q$,因为保证了 $N=pq$,所以我们相当于要找到 $N$ 的一个质因数。

显然 $N$ 的规模这么大不能通过 $O(\sqrt N)$ 的方法去暴力查找,于是就想到了 Pollard_Rho(再合适不过了,因为虽然 $N$ 很大,但是只需要分解质因数一次)。其实 Pollard_Rho 只是找到 $N$ 的除了 $1$和$N$ 的因数而非质因数,但是这道题保证了 $N$ 的因数只有 $1,p,q,N$ ,所以我们只要 Pollard_Rho 一次就可以了。

于是我们就可以求出 $p,q$ 进而求出 $r$。

接下来就要求解 $ed\equiv1\pmod r$ 了,其实 $d$ 就是 $e$ 在模 $r$ 下的逆元。因为 $e,r$ 互质,所以 $d$ 一定存在。

由 $ed\equiv1$ 可得 $ed+kr=1$ 即 $d\times e+k\times r=gcd(e,r)$ ,那么就可以 EXGCD 了。

最后直接快速幂计算 $c^d\bmod N$。


Part3. 小技巧

注意到这里的变量规模,当两个 $2^{62}$ 规模的数相乘时,还没等你取模就溢出了。所以需要一些处理。

其中一种是 $O(\log)$ 的“龟速乘”,处理核心是乘法化 $\log$ 次加法,就像快速幂一样:

1
2
3
4
5
6
7
8
9
long long Mul(int Va,int Vb,int Vm){ //Va*Vb%Vm
long long ret=0;
while(Vb){
if(Vb&1) ret=(ret+Va)%Vm;
Va=(Va+Va)%Vm;
Vb>>=1;
}
return ret;
}

另外一种是玄学的快速乘……我也不知道为什么它是正确的:

1
2
3
4
5
long long Mul(int Va,int Vb,int Vm){ //Va*Vb%Vm
long long Vc=(long double)Va/Vm*Vb;
long long res=(unsigned long long)Va*Vb-(unsigned long long)Vc*Vm;
return (res%Vm+Vm)%Vm;
}

Part4. 源代码

Hint. 在主函数中,我一般在变量名之前加一个 V 表示这是题面中给出的变量。比如说题面中的变量 $c$ 在代码中定义为 Vc

【点击展开/折叠代码
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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ll Cc[]={2,3,5,7,11,13,17,19,23,29};

ll Mul(ll Va,ll Vb,ll Vm){
ll Vc=(ld)Va/Vm*Vb;
ll Rr=(ull)Va*Vb-(ull)Vc*Vm;
return (Rr+Vm)%Vm;
}
ll QPow(ll Va,ll Vb,ll Vm){
ll Rr=1;
while(Vb){
if(Vb&1) Rr=Mul(Rr,Va,Vm);
Va=Mul(Va,Va,Vm);
Vb>>=1;
}
return Rr;
}
bool MillerRabin(ll Va,ll Vd,ll Vn){
ll Vx=QPow(Va,Vd,Vn);
if(Vx==1 || Vx==Vn-1) return true;
while(Vd!=Vn-1){
Vd*=2;Vx=Mul(Vx,Vx,Vn);
if(Vx==1) return false;
if(Vx==Vn-1) return true;
}
return false;
}
bool CKPr(ll Vn){
for(int i=0;i<10;i++){
if(Vn==Cc[i]) return true;
if(Vn%Cc[i]==0) return false;
}
ll Vd=Vn-1;
while(Vd%2==0) Vd/=2;
for(int i=0;i<10;i++)
if(!MillerRabin(Cc[i],Vd,Vn))
return false;
return true;
}
ll GCD(ll Va,ll Vb){return Vb? GCD(Vb,Va%Vb):Va;}
ll ABS(ll Vx){return Vx<0? -Vx:Vx;}
ll PollardRho(ll Vn){
for(int i=0;i<10;i++)
if(Vn%Cc[i]==0)
return Cc[i];
ll Va=1ll*rand()*rand()%(Vn-2)+2,Vb=Va,
Vg=1,Vc=1ll*rand()*rand()%(Vn-1)+1;
while(Vg==1){
Va=(Mul(Va,Va,Vn)+Vc)%Vn;
Vb=(Mul(Vb,Vb,Vn)+Vc)%Vn;
Vb=(Mul(Vb,Vb,Vn)+Vc)%Vn;
Vg=GCD(ABS(Va-Vb),Vn);
}
return Vg;
}
ll MinP(ll Vn){
if(Vn==1) return (1ll<<60);
if(CKPr(Vn)) return Vn;
ll Vm=PollardRho(Vn);
return min(MinP(Vm),MinP(Vn/Vm));
}
ll EXGCD(ll Va,ll Vb,ll &Vx,ll &Vy){
if(Va==1 && Vb==0){
Vx=1;Vy=0;
return 1;
}
ll Vx_,Vy_;
ll Rr=EXGCD(Vb,Va%Vb,Vx_,Vy_);
Vy=Vx_-Va/Vb*Vy_;
Vx=Vy_;
return Rr;
}
int main(){
ll Ve,Vn,Vc;
scanf("%lld%lld%lld",&Ve,&Vn,&Vc);
ll Vp=PollardRho(Vn),Vq=Vn/Vp; //计算 p,q
ll Vr=(Vp-1)*(Vq-1);
ll Vd,Vk;
EXGCD(Ve,Vr,Vd,Vk); //扩展欧几里得
Vd=(Vd%Vr+Vr)%Vr; //!!!
printf("%lld %lld\n",Vd,QPow(Vc,Vd,Vn));
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com,欢迎提问!

0%