sage中求解离散对数我目前知道的四个函数：discrete_log(a,base,ord,operation)，discrete_log_rho(a,base,ord,operation)，discrete_log_lambda(a,base,bounds,operation)，bsgs(base,a,bounds,operation)；这四个函数分别是通用的求离散对数的方法，求离散对数的Pollard-Rho算法，求离散对数的Pollard-kangaroo算法（也称为lambda算法）以及小步大步法；

参数说明：对于discrete_log与discrete_log_rho，求解以base为底，a的对数；ord为base的阶，可以缺省，operation可以是'+'与'*'，默认为'*'；对于discrete_log_lamda，bounds是一个区间(ld,ud)，需要保证所计算的对数在此区间内。

下面分别举例使用这些函数对ElGamal的分析与Ecc的分析。

//首先找到一个素数p
p=next_prime(200520052005)
//p=20052005200520052031
//定义有限域GF(p)
G=GF(p)
//找一个模p的原根
gp ('znprimroot(20052005200520052031)')
//Mod(6, 20052005200520052031)，说明6是模p的原根
//因此6可作为生成元
g=G(6)
//生成私钥
x=G(ZZ.random_element(p-1))
//公钥y=g^x mod p，由于已经定义在GF(p)上，因此g**x就是g^x mod p
y=g**x
//计算离散对数的通用方法
discrete_log(y,g)
//验证是否求解正确
discrete_log(y,g)==x
//True
//计算离散对数的lambda方法
discrete_log_lambda(y,g,(floor(ZZ(x)/2),2*ZZ(x)))
//同样正确求解
//小步大步法计算离散对数
bsgs(g,y,(floor(ZZ(x)/2),2*ZZ(x)))

上面是以discrete_log举例，discrete_log_rho参数列表与discrete_log一致，因此用法相同；只不过，由于discrete_log_rho是基于随机性的概率型算法，因此不一定每次都能找到，不过多一个方法总归是好的；其次，https://xz.aliyun.com/t/2780里面详细介绍了Pollard Rho算法，这个算法起作用是有条件的。

此算法适用于生成元的阶的素因子都是大数的情形，计算元素的阶的函数如下。

//加法阶
n=g.order();n
//乘法阶
n=g.multiplicative_order();n

可以看到加法阶比乘法阶大1。

下面介绍在椭圆曲线上求解离散对数。下例为2013年SECCON CTF quals 中的 Cryptanalysis。

a = 1234577
b = 3213242
n = 7654319
//有限域GF(n)上的椭圆曲线y^2 = x^3 + a*x + b mod n
E = EllipticCurve(GF(n), [0, 0, 0, a, b])
//生成元
base = E([5234568, 2287747])
//公钥
pub = E([2366653, 1424308])
//求解私钥，通用方法；注意这里的运算要换成加法
discrete_log(pub,base,operation='+')
//求解私钥，Rho方法
discrete_log_rho(pub,base,operation='+')
//此情形Rho方法也可以求解，而且可以感觉到比通用方法要快
///求解私钥，lambda方法
discrete_log_lambda(pub,base,(floor(1584718/2),2*1584718),operation='+')
//小步大步发计算离散对数
bsgs(base,pub,(floor(1584718/2),2*1584718),operation='+')