题解 P5451 【[THUPC2018]密码学第三次小作业】

2019-07-13 16:06:03


一道不错的数论题。

因为 $e_1\perp e_2$ ,所以会存在一对数 $s,t$ ,满足 $e_1s+e_2t=1$ 。

我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形:

$$\displaystyle\begin{aligned}m\bmod N=&m^{e_1s+e_2t}\bmod N\\=&m^{e_1s}m^{e_2t}\bmod N\\=&{c_1}^s{c_2}^t\bmod N\end{aligned}$$

于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ,所以可以直接 exgcd 求出 $s$ 和 $t$ 。

然而这里求出的 $s$ 和 $t$ 一正一负,为了方便我们假设 $s$ 是负数。

根据常规方法,有 ${c_1}^{-|s|}\bmod N={c_1}^{\varphi(N)-|s|}\bmod N$ ,然而求 $\varphi(N)$ 的复杂度过大,所以这样是不行的。

根据小学奥数可以得到 ${c_1}^{-|s|}\bmod N=\left(c_1^{-1}\right)^{|s|}\bmod N$ ,于是我们只要求出 $c_1^{-1}$ 即可。

设 $d=c_1^{-1}\bmod N$ ,可以得到 $c_1d+kN=1$ 。那么直接 exgcd 求出 $d$ 即可。

代码见blog