关于离散对数问题的一些想法(2011年2月28日更新)

这个方法是在考究二进制表达方式时想到的。所谓离散对数问题(DLP),意思大概是选取一个大的素数p,再选一个原根a,对于随机选取的x,已知a^x要计算出x来是困难的。因为x=log(a^x)(对数以a为底),而这个对数是在模p的情况下计算的,所以叫离散对数问题。下面简单说一下自己的想法:

假定要计算a^x=b的根x。首先证明了原根不可能是二次剩余的,于是,如果b是二次剩余,那么x必定是偶数,否则x必定为奇数,这样通过对b的计算,可以得到x的低一位。如果b是非二次剩余,那么令b=b*(a^(-1)),这样b必定是二次剩余的,因为(x-1)为偶数。于是两边计算平方根,这样原问题等价于计算a^y=b^(1/2)的跟,y=x/2。也就是说只要计算出y,就等计算出x。显然y<x,如此递归下去,最后必定有a^y=a,这样我们可以认为在指数模(p-1)的情况下y=1。然后再反推出x,进而给出了原始的解。不过在验证的时候发现了几个问题:
一、平方根有两个。如果每个都去尝试的话,其复杂度和平凡的尝试法是没区别的。于是我想到了如果保存递归时产生的b,如果发现当前的b在前面出现过,则忽略这个方程,因为a是原根,只要x不等于y,就必定有a^x不等于a^y。
二、原根的计算问题。因为要找原根,对于大的素数来说,找原根是困难的(可能还更好的方法自己不知道)。
三、复杂度分析。尽管有剪枝条件了,但是对于某些x来说,仍然无法从理论上证明,这个算法的复杂度是优于平凡的算法或者已知的算法的。猜测最好情况下的复杂度为O(logp)。
看得好郁闷,希望有高人指点一二,特别是最后的复杂度分析。请给我留言,谢谢了。

比如说p=13,g=2,x=5,g^x=6,2^(-1)=7,
计算2^x0=6。因为6是非二次剩余。所以等价于计算2^x1=6*7=3.
计算2^x1=3。因为3是二次剩余。所以等价于计算2^x2=4和2^x2=9。
计算2^x2=4。显然有x2=2,于是x1=x2*2=4,x0=x1+1=5,算法终止。
计算2^x2=9。因为9是二次剩余,所以等价于计算2^x3=3和2^x3=10。因为2^x1=3与2^x3=3是相同的,所以忽略这个方程。
计算2^x3=10。因为10是二次剩余。所以等价于计算2^x4=6和2^x4=7。因为2^x4=6与2^x0=6相同,所以忽略这个方程。
计算2^x4=7。因为7是非二次剩余。所以等价于计算2^x5=10。因为2^x5=10与2^x3=10是相同的,所以忽略这个方程。

特别指出,这个极类似的算法在1984年就已经有人提出过了,DLP和一个principal square root problem有关,可以参考这篇文章:
《How to generate cryptographically strong sequences of pseudo random bits》

打赏

发表评论

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