gmpy/离散对数

• 本文约709字,阅读大致需要2分钟 • Security

前几天做一个解离散对数的题用到了gmpy,它是GMP的Python封装,用来算大数。

这里记两笔。首先是大整数需要用mpz对象,例如:

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)

判断大数是否是质数:is_prime(p)(求离散对数其实用不着)

求逆元x−1x^{-1}:invert(x, p)。例如,y = invert(x, p)则(x∗y) mod p=1(x * y) \bmod p = 1

幂取模:pow(x, n, p),即xn mod px^n \bmod p。结果仍为mpz。

mpz对象可以直接用在dict中做键值。

题目中提供的方法是分治,将解xx拆成两部分x0∗B+x1x_0 * B + x_1,其中BB是2的整数次方幂(约为xx上限的开方,例如,如果xx的范围是2402^{40},则B=220B=2^{20}。这样x0x_0、x1x_1分别小于BB,将方程整理成x0x_0、x1x_1分别在等式左右(其它部分都是常数了),然后穷举x0x_0对应的值(计算2202^{20}次,保存所有结果),然后穷举所有的x1x_1对应的值,如果发现之前保存的结果中有匹配,则输出对应的x0x_0、x1x_1,从而算出xx。由于将搜索范围变成了N\sqrt{N},所需的时间也就大大减少了。