一道练习题,毕竟学了 Miller_Rabin 和 Pollard_Rho 还是得运用一下 ~
Part1. 题意(简化版)
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 | long long Mul(int Va,int Vb,int Vm){ //Va*Vb%Vm |
另外一种是玄学的快速乘……我也不知道为什么它是正确的:
1 | long long Mul(int Va,int Vb,int Vm){ //Va*Vb%Vm |
Part4. 源代码
Hint. 在主函数中,我一般在变量名之前加一个 V
表示这是题面中给出的变量。比如说题面中的变量 $c$ 在代码中定义为 Vc
。
1 | /*Lucky_Glass*/ |
The End
Thanks for reading!
Email: lucky_glass@foxmail.com,欢迎提问!