这个方法是在考究二进制表达方式时想到的。所谓离散对数问题（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》