前言
难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)
其实是因为这个Reverse的题里面幂指数是质数，所以会跟模数互质，然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.
OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…
模质数的K次剩余
已知$a$, $b$, $p$, 求使得
$$
x^{a} \equiv b \quad(\bmod \ p)
$$
成立的所有 $x$. 其中 $p$ 是质数.
由于 $p$ 是质数, 所以 $p$ 存在原根 $g$ , 此时对于模 $p$ 意义下的任意数 $w$ ($0\le w \le p-1$) 存在唯一的 $i$ ($0\le i \le p-1$) 使得 $w\equiv g^i\quad(\bmod \ p)$.
由此可以将最终的答案用 $g$ 来表示: $x=g^{c}$, 带入上式转化为求解
$$
(g^{c})^{a}\equiv (g^{a})^c\equiv b \quad(\bmod \ p)
$$
此时 $g$, $a$, $b$, $p$, 已知, 只需要解出来 $c$. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 $\mathcal{O}(\sqrt{p})$ 时间内得到一个特解 $x_0 \equiv g^{c} \quad(\bmod \ p)$.
在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 $g^{\varphi(p)}\equiv 1 \quad(\bmod \ p)$, 因此:
$$
\forall t \in \mathbb{Z}, x^{a} \equiv g^{c \cdot a+t \cdot \varphi(p)} \equiv b \quad(\bmod \ p)
$$
因此所有的解为:
$$
\forall t \in \mathbb{Z}, a \mid t \cdot \varphi(p), x \equiv g^{c+\frac{t \cdot \varphi(p)}{a}} \quad(\bmod p)
$$
上面幂次部分要能整除必须要有$\frac{a}{\operatorname{gcd}(a, \varphi(p))} \mid t$, 可以设 $t=\frac{a}{\operatorname{gcd}(a, \varphi(p))} \cdot i$, 于是得到所有的解为:
$$
\forall i \in \mathbb{Z}, x \equiv g^{c+\frac{\varphi(p)}{\operatorname{gcd}(a, \varphi(p))} \cdot i} \quad(\bmod p)
$$
HDU 3930 Broot 代码:
继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”
