从BSGS到Pohlig-Hellman

· · 个人记录

从BSGS到Pohlig-Hellman

两个求解离散对数a^x\equiv b\pmod m的算法。

BSGS

由费马小定理可知x\in[0,\varphi(m))，故设x=i\sqrt{\varphi(m)}-j，其中i\in[0,\sqrt{\varphi(m)}],j\in[0,\sqrt{\varphi(m)}-1],i,j\in\Z^*，有点类似分块，显然这样的组合可以表示[0,\varphi(m))中的任意整数，然后得到a^{i\sqrt{\varphi(m)}-j}\equiv b\pmod m，移项可得a^{i\sqrt{\varphi(m)}}\equiv a^jb\pmod m，然后枚举j，用hash记录a^jb，然后枚举i，看一下有没有一个a^jb和当前的a^{i\sqrt{\varphi(m)}}相等。时间复杂度\mathcal O(\sqrt{\varphi(m)})

Pohlig-Hellman

但是如果m如此之大，以至于\mathcal O(\sqrt{\varphi(m)})​是无法接受的，何以为之？

考虑利用二向箔原根把乘方降维打击变成乘法。即令g为m的一个原根。a\equiv g^A,b\equiv g^B\pmod m。则有g^{Ax}\equiv g^B\pmod m，即Ax\equiv B\pmod{\varphi(m)}，这个东西就灰常好解了。

问题在于如何求g^A\equiv a\pmod m，我们发现这个问题和上个问题几乎是等价的，但是现在a是原根。

对\varphi(m)分解质因子\varphi(m)=\prod p_i^{k_i}，对于每个p_i把x写成p_i进制，x\equiv \sum p_i^jx_j\pmod {p_i^{k_i}}

接下来，在a^x\equiv b \pmod m左右两边取r=\frac{\varphi(m)}{p_i}次方，就有

a^{rx}\equiv a^{r\sum p_i^jx_j}\equiv a^{rx_0}\equiv b^{r}\pmod m

那是因为从一次项开始，都因为a^{\varphi(m)}\equiv 1被约掉了。由于a是m的原根，因此它不会被\varphi(m)/p_i约掉。

由于x_0\in[0,p_i)我们可以暴力枚举并判断是否合法。

然后在a^x\equiv b \pmod m左右两边取\frac{\varphi(m)}{p_i^2}次方，从二次项开始，都因为a^{\varphi(m)}\equiv 1被约掉了，于是得到x_1。

以此类推，直到得到整个x。由于a是原根，因此不用担心x的信息丢失。然后再用CRT把所有x合并即可。