离散对数的求解

1.暴力

2.Baby-step giant-step 

3.Pollard’s ρ algorithm

……

下面搬运一下Baby-step giant-step 的做法

 

这是在 上看到的，比较容易理解。

而且，里面的代码写得简洁明了。

写一下自己理解和自己照着写了一遍

原文代码：

def bsgs(g, y, p):    m = int(ceil(sqrt(p - 1)))    S = {pow(g, j, p): j for j in range(m)}   #在字典S中存放了g^j和对应的j    gs = pow(g, p - 1 - m, p)                 #求解的是baby step中的值，也就是g^(-m),其实就是g^m mod p的逆元，也就可以使用egcd来求解    for i in range(m):        if y in S:            return i * m + S[y]               #S[y]取出的是此时y对应的i        y = y * gs % p                        #如果baby step的值和 giant step的值不相等，继续执行baby step    return None

 

照着写一遍的代码

#求解离散对数问题import mathdef egcd(a,b):    r0,r1,s0,s1=1,0,0,1    n=b    while(b):        q,a,b=a//b,b,a%b        r0,r1=r1,r0-q*r1        s0,s1=s1,s0-q*s1    return r0%n             #拓展欧几里得返回的三个值是，a是a和b的最大公因数，r0和s0分别是ax+by=c中的一组解x和y，【此时只是选择返回一个r0，因为得到的是ax+by=gcd(a,b)中的x即可，有的时候x或者y可能为负数，在求解正数的逆元的时候负数要对n再次求模运算    #求解离散对数就是，X=G^a mod P,其中给出X,G,P的值，要求解的是 a的值，此处采用的是Baby step giant step的方法def bsgs(x,g,p):                  #求解x=g^a mod p中的a，其中g是生成元    m=math.ceil(math.sqrt(p-1))   #m的值是 p-1开平方后向上取整    bstep={pow(g,j,p):j for j in range(m)}              #每一次 j 的增加表示 “baby-step”，一次乘上g，字典S中存了所有的g^j(j

 

继续学习其他的做法

参考资料：