离散对数问题与BSGS算法

离散对数(discrete logarithm)指的是解形如\(a^x\equiv b(mod\ m)\)的方程的一类问题,其中\(a,b,m\)为已知数,\(x\)为未知数。实际上,这个问题现在还并没有多项式的解法,最有效的解法时间复杂度与\(m\)最大的质因数密切相关,也正是由于这个特点,离散对数问题在密码学中有着广泛应用。

这篇文章将讨论解决离散对数问题的大步小步算法(baby-step giant-step algorithm),它能够以远快于枚举的速度解决问题,在算法竞赛中也非常实用。

为了方便讨论,我们将从较简单的情形开始,逐步深入到一般情况。

\(m\)为质数

不妨设\(0<a,b<m\),因为若\(ab=0\)则解是易知的,否则都可以简单转化以后变为我们假设的情况。根据费马小定理,\(a^{m-1}\equiv 1(mod\ m)\),故原方程若有解,则一定在\([0,m-1)\)内有一个解。同理,我们只要找出了方程在\([0,m-1)\)内的所有解,也就能找出方程的所有整数解。

设方程有解\(x_0,x_0\in[0,m-1)\),则根据带余除法的性质,\(x_0\)可以被写作\(q\lfloor\sqrt m\rfloor+r\),其中\(q,r\in[0,\lfloor\sqrt m\rfloor]\),\(\lfloor\sqrt m\rfloor\)表示\(\sqrt m\)向下取整(换句话说,\(q=x_0\ div\ \lfloor\sqrt m\rfloor,r=x_0\ mod\ \lfloor\sqrt m\rfloor\))。

另一方面,由于\(m\)是质数,所以\(a\)有模\(m\)的乘法逆元,则\(a^{x_0}\equiv b(mod\ m)\)可以化作\(a^{q\lfloor\sqrt m\rfloor}\equiv ba^{-r}(mod\ m)\)。而想要确定\(x_0\)的值,只需确定\(q,r\)的值即可。我们可以直接算出\(a^{\lfloor\sqrt m\rfloor}\)的值,然后判断该值是否在数列\(b,ba^{-1},…,ba^{-\lfloor\sqrt m\rfloor}\)中,若是,则我们找到了一组\(q,r\),也就找到了方程的一个解。接下来我们依次枚举\(a^{2\lfloor\sqrt m\rfloor},a^{3\lfloor\sqrt m\rfloor},…,a^{k\lfloor\sqrt m\rfloor}\)的值是否在数列中,直到\(k\lfloor\sqrt m\rfloor\geq m-1\),我们相当于遍历方程所有可能的解。

不难发现,\(k\)的值是\(O(\sqrt m)\)的,而除了第一次计算\(a^{\lfloor\sqrt m\rfloor}\)的值时间复杂度是\(O(\log m)\),之后都可以\(O(1)\)进行枚举,所以总的枚举复杂度为\(O(\sqrt m)\)。判断一个值是否在一个固定的数列中则有多种解决方式,如果我们采用C++中方便的map,则BSGS算法总时间复杂度为\(O(\sqrt m\log m)\),如果采用哈希表,则总时间复杂度为\(O(\sqrt m)\)。

至此,我们完成了BSGS算法,并解决了离散对数问题中\(m\)为质数的情况。

\(a\)与\(m\)互质

为了解决这种情形,我们需要考察在上一种情况中,有哪些地方用到了\(m\)为质数的性质。

一是费马小定理仅当\(m\)为质数时成立,这很好办,我们只需将其改为欧拉定理,即\(a^{\phi(m)}\equiv 1(mod\ m)\),这样我们寻找解的范围仍可以限制在\([0,\phi(m))\)中,且时间复杂度也可以同样保证为\(O(\sqrt m)\)。

二是\(a\)的乘法逆元的存在性,当\(a\)与\(m\)互质时乘法逆元仍是存在的,所以我们直接沿用之前的算法即可完全解决这种情况。

一般情况

在一般情况下,我们即无法限定寻找解的范围,也不能保证\(a\)的乘法逆元的存在性,所以我们无法直接沿用BSGS算法。换个角度,我们不妨考虑对原方程做一些变换,使得变换后的方程能够满足前两种情形之一,求解后再将其逆变换得到原方程的解。

将原方程写作类似不定方程的形式:\(a^x+my=b\),并设\(d=gcd(a,m)\),若\(d\not\mid b\),则方程是无解的,否则将等式两边同除以\(d\)得\(\frac{a}{d}a^{x-1}+\frac{m}{d}y=\frac{b}{d}\),方程的解不发生变化。

重新构建同余方程\(\frac{a}{d}a^{x-1}\equiv\frac{b}{d}(mod\ \frac{m}{d})\),由于\(\frac{a}{d},\frac{m}{d}\)一定互质,故\(\frac{a}{d}\)有模\(\frac{m}{d}\)的乘法逆元\((\frac{a}{d})^{-1}\),方程等价于\(a^{x-1}\equiv\frac{b}{d}(\frac{a}{d})^{-1}(mod\ \frac{m}{d})\)。令\(x’=x-1\),\(b’=\frac{b}{d}(\frac{a}{d})^{-1}\),\(m’=\frac{m}{d}\),则我们得到了一个规模小于原问题的新离散对数问题\(a^{x’}\equiv b'(mod\ m’)\)。

注意到上述过程中,方程的模数在不断减小,所以最后一定会到达\(a\)与\(m\)互质的情况,此时再使用BSGS算法即可。当我们知道了\(x’\)的值后,算出\(x\)的值是平凡的。由于每次对方程变形,我们都是将模数除去了它的一个因数,所以总变形次数不会超过\(O(\log m)\)次,整个算法的瓶颈仍然在BSGS上。

至此,我们完整地给出了离散对数问题的一个解法,其总时间复杂度为\(O(\sqrt m)\),虽然不尽人意,但在算法竞赛或工程中已经足够使用。

目前最佳的解决离散对数问题的算法仅能达到\(O(\sqrt p)\)的时间复杂度,其中\(p\)为\(m-1\)最大的质因数,这也告诉我们,如果要给一道题目中设计求解离散对数的环节,不仅模数\(m\)要足够大,\(m-1\)也需要有一个很大的质因数,数据才足够强力~

发表评论

电子邮件地址不会被公开。 必填项已用*标注