gmpy/离散对数

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

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

p = mpz www.zzzyk.com

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

求逆元 (x^-1)：invert(x, p)。例如， y = invert(x, p) 则 x*y % p = 1

幂取模：pow(x, n, p)，即 (x ^ n) % p。结果仍为 mpz。

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

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

补充：综合编程 , 其他综合 ,