OI - 密钥破解(POJ) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - 密钥破解(POJ)

发表于 更新于 分类于 Valine：

一道练习题，毕竟学了 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，欢迎提问！