扩展大步小步法解决离散对数问题

离散对数(Discrete Logarithm)问题是这样一个问题,它是要求解模方程

 a^x \equiv b \pmod m

这个问题是否存在多项式算法目前还是未知的,这篇文章先从 m 是质数开始介绍大步小步法(Baby Step Giant Step)来解决它,之后再将其应用到 m 是任意数的情况。这个算法可以在 \mathcal O(\sqrt m) 的时间内计算出最小的 x,或者说明不存在这样一个 x

题目链接:BZOJ-2480SPOJ-MODBZOJ-3239

首先解决 m=p 是质数的情况,我们可以设 x = A \lceil \sqrt{p} \rceil + B,其中 0 \leq B < \lceil \sqrt{p} \rceil0 \leq A < \lceil \sqrt{p} \rceil,这样的话就变成求解 AB 了,方程也变成

 a^{A\lceil \sqrt{p} \rceil + B} \equiv b \pmod p

可以在两边同时乘以 a^B 的逆元,由于 p 是质数,这个逆元一定存在,于是方程变成

 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^{-B} \pmod p

由于 A, B 都是 \mathcal O(\sqrt p) 级别的数,可以先计算出右边这部分的值,存入 Hash 表,然后计算左边的值,在 Hash 表中查找,只要按照从小到大的顺序如果有解就能够找到最小的解,由于两边都只有 \mathcal O(\sqrt p) 个数,因此时间复杂度是 \mathcal O(\sqrt p) 的,这样 m 是质数的情况就解决了

一个优化:我们可以设 x = A \lceil \sqrt{p} \rceil - B,其中 0 \leq B < \lceil \sqrt{p} \rceil0 < A \leq \lceil \sqrt{p} \rceil + 1,这样的话化简后的方程就是

 a^{A\lceil \sqrt{p} \rceil} \equiv b\cdot a^B \pmod p

就可以不用求出逆元,要注意只是不用求出逆元,而不是没有用到逆元的存在

现在来看 m 不是质数的情况,同样可以设 x = A \lceil \sqrt{m} \rceil + B,根据上面的推导,会发现需要用到的性质就是 a^B 的逆元存在,所以当 ma 互质的时候这个方法仍然有效!

如果 (m, a) \neq 1 该怎么办呢?我们要想办法把方程转化为 (m, a) = 1 的情况

把要求的模方程写成另外一种形式

 a^x + km = b, k \in \mathbb Z

g = (a, m),这样的话可以确定如果 g \nmid b 那么该方程一定无解,所以当 g \mid b 的时候,在方程左右两边同时除以 g

 \frac{a}{g} a^{x-1} + k \frac{m}{g} = \frac{b}{g}, k \in \mathbb{Z}

这样便消去了一个因子,得到方程

 \frac{a}{g} a^{x-1} \equiv \frac{b}{g} \pmod {\frac{m}{g}}

m' = \frac{m}{g}, b' = \frac{b}{g} \left (\frac{a}{g}\right)^{-1}(这里不可以把 g 消掉),就可以得到新的方程

 a^{x'} \equiv b' \pmod {m'}

得到解之后原方程的解 x = x' + 1,不断重复这个过程最后一定会得到一个可以解的方程,套用刚刚的大步小步法解出后即可。要注意的是在这个过程中如果某一步发现 b'=1,那么就可以直接退出,因为这时候已经得到了解

NOTE:上面这个过程是可能执行多次的比如说 (a, m) = (6, 16) \rightarrow (6, 8) \rightarrow (6, 4) \rightarrow (6, 2)

下面的是代码,题目是文章开头给的链接(注:题目应该是加了一组模1的数据,原先的代码才会WA

 

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2015/05/discrete-logarithm-problem

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

15 thoughts on “扩展大步小步法解决离散对数问题

  1. 喜欢学长的棒棒哒数学文! 我想问问开头说的"由于 p 是质数,这个逆元一定存在". 但是(a^b, p)不一定等于1?

    1. a/g 已经用 t 记录下来了,在后面计算的时候左侧有乘上 t

  2. 题主我想请教一下,如果题目本身所给出的就是对数形式,像是这个式子: log_23\ mod\ 100 为什么给出的模数并非是$p$而是$\phi (p)$?一直没能理解这里是怎么转化的(这个题的题解给出的$p$是101来的……)

    1. 我不确定你说的是不是这个,不过比如说有个p,然后你知道

      a \equiv b \pmod p

      那么两边取指标(也就是对数)

      \text{ind} a \equiv \text{ind} b \pmod {\phi(p)}

      直观上理解就是 m^r \equiv b \pmod p 以及 m^{\phi(p)} \equiv 1 \pmod p 所以前面一个式子乘后面这个式子在指数上面相当于模了 \phi(p)

      1. 看了一下你的回答,似乎是搞明白了

        两边同时取对数的那个等价我是第一次见,不过我手边的书里有一条性质和这个很相似:

        g^h\equiv g^k \pmod n \Leftrightarrow h\equiv k\pmod{\phi(n)}

        如果把你的ab替换成g^hg^k的话:

        Ind_gg^h\equiv Ind_gg^k\equiv h\equiv k\pmod{\phi(n)}

        他们至少看上去应该是等价的,虽然我从没有那么考虑过……

        刚刚用mathematica跑了一下,2是模101的原根,而恰好\phi (101)=100,所以这个问题就该转化成了:

        x\equiv log_23\equiv Ind_23\pmod{100} \Rightarrow 2^x\equiv 2^{Ind_23}\equiv 3\pmod{\phi(100)}

        然后这个问题就转化成了标准形式的离散对数问题,可以用大步小步求解了?

        不知道这个理解对不对 (⊙ˍ⊙)……

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.