CWYAlpha

Just another WordPress.com site

Thought this was cool: gmpy/离散对数

leave a comment »


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

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

p = mpz(13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171)

判断大数是否是质数: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),所需的时间也就大大减少了。


0

   

0

IT 牛人博客聚合网站(udpwork.com) 聚合
|
评论: 0
|
10000+ 本编程/Linux PDF/CHM 电子书下载

from IT牛人博客聚合网站: http://www.udpwork.com/item/8414.html

Written by cwyalpha

十月 16, 2012 在 2:43 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: