前言
难以置信, 遇到这个问题竟然是因为做一道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, 求使得
xa≡b(mod p)
成立的所有 x. 其中 p 是质数.
由于 p 是质数, 所以 p 存在原根 g , 此时对于模 p 意义下的任意数 w (0≤w≤p−1) 存在唯一的 i (0≤i≤p−1) 使得 w≡gi(mod p).
由此可以将最终的答案用 g 来表示: x=gc, 带入上式转化为求解
(gc)a≡(ga)c≡b(mod p)
此时 g, a, b, p, 已知, 只需要解出来 c. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 O(√p) 时间内得到一个特解 x0≡gc(mod p).
在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 gφ(p)≡1(mod p), 因此:
∀t∈Z,xa≡gc⋅a+t⋅φ(p)≡b(mod p)
因此所有的解为:
∀t∈Z,a∣t⋅φ(p),x≡gc+t⋅φ(p)a(modp)
上面幂次部分要能整除必须要有agcd(a,φ(p))∣t, 可以设 t=agcd(a,φ(p))⋅i, 于是得到所有的解为:
∀i∈Z,x≡gc+φ(p)gcd(a,φ(p))⋅i(modp)
HDU 3930 Broot 代码:
继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”