题解 P4454 【[CQOI2018]破解D-H协议】

· · 个人记录

先给出来啥叫离散对数问题吧……

给出这个同余式

X^{c}\equiv Y(modP)

现在已知X,Y,P求c，这就是离散对数问题

当然为了保证这个方程有唯一解，我们保证X是P的原根，所谓原根，就是对于任意的0<Y<P刚才的方程都有唯一解的X值了……，有一个推论是如果X是原根，那么X^imodP(i∈(0,p))刚好是1~p-1的一个全排列，

不过这和我们接下来讲的BSGS算法没有太大关系就是了，原根的存在只是为了保证离散对数问题解的唯一性就是了……

对于离散对数问题来讲目前没有多项式算法(数论范畴认为只有O(logN)才算多项式算法，其他的例如O(N)O(\sqrt{N})是指数算法)，但是有一O(\sqrt{N})的分块算法，就是我们说的BSGS算法了

首先先考虑暴力

由于 A^{p-1}\equiv 1(modP)就是费马小定理，所以我们可以1~p-1的枚举c，然后判定X^c是否modP同余于Y，但是这样有点傻了……，所以我们考虑分块大法

我们令bs=\sqrt{P-1}然后将c用c/bs和cmodbs来表示c

现在我们枚举c/bs的值

那么现在的同余式变成了

X^{cmodbs} \equiv Y×inv(X^{c/bs})(mod P)

我们现在需要快速查找X^{cmodbs}是否存在，发现这部分的指数最大不过bs，所以可以打表，用一个map存起来

我们发现inv(X^{c/bs})的值最多不过(p-1)/bs种所以也可以打表

然后求解离散对数的时候我们直接大力枚举c/bs然后每次到对应的map里去查有没有这个值就可以了，使用了map是因为我们得记一个这个值到底是X的多少次幂……

所以所谓的BSGS不过是打了两个根号N的表的高端暴力而已

然后我们就暴力离散对数出a,b然后快速幂计算一发就可以了~

上代码~