找回密码
 欢迎注册
查看: 17353|回复: 14

[讨论] 快速求大整数关于 2^n 的模逆

[复制链接]
发表于 2009-2-23 14:44:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
与普通的求模逆不同,这里的“模”本身是个 perfect power

即:已知正整数 n 及 b(b为奇数),
求:整数x,使得 bx≡1 (mod 2^n)

由于模的特殊性,不知可有什么特别的快速算法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-23 14:51:09 | 显示全部楼层
现有一个比较好的递归算法,与大家分享一下:

若:$a -= b^-1\quad(mod m)$,
则:$x -= a*(2-a*b) -= b^-1\quad (mod m^2)$
简证:令 $a*b = k*m+1$,则 $bx = 1-(ab - 1)^2 = 1-k^2*m^2 -= 1\quad (mod m^2)$

对于 $m=2^n$,显然可令初始值:$x_1=1-=b^-1\quad (mod 2)$,
再用上面这个公式可以很好的计算出我们想要的结果(迭代次数为 $|~log_2(n)~|$ 次)。

但每次迭代需要两次大数乘法,可否有更适合大数运算的算法?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-24 10:10:21 | 显示全部楼层
我自己又发现了一种更便于无符号系统实现的快速模幂算法,
不知谁有兴趣一同来探讨?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-24 10:25:09 | 显示全部楼层


借我一个alpha64位工作站
我和你讨论
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-18 14:56:52 | 显示全部楼层
在 2#,给出了一个递归的算法。

其实对于某些特殊的底数,还有更快捷的算法。

比如求 PowMod( 4294770689, -1, 4294967296 ) ?
其中 4294967296 = 232,4294770689 = 0xFFFD0001

若用 2# 的算法需要递归 5 次计算得到结果。
而更快的则用如下公式一步得到:4294967296+2-4294770689 = 196609
验证一下:4294770689 * 196609 = 844390570393601 = 0x 2FFF8 0000 0001

该算法依据是我今天偶然独立发现的定理(不知前人是否已有类似结论):
若:$m | (p-1)^2$,则 $p^(-1) -= m+2-p\quad(mod m)$
证: $p*(m+2-p) - 1 = p*m - (p-1)^2 -= 0\quad(mod m) => p^(-1) -= m+2-p\quad(mod m)$

当模数为完全平方数,且其算术平方根整除于“底数减一”时(即:$sqrt(m)|(p-1)$),
运用上述定理求模逆相当高效。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-18 19:03:36 | 显示全部楼层
若:m|(p-1)^2,则 p^(-1)≡m+2-p  (modm)

我看不明白,p^(-1)还是整数吗
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-18 19:44:47 | 显示全部楼层
是,就是找个整数q
使得p * q = 1 (mod m)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-3-18 19:56:49 | 显示全部楼层
对,p^(-1) 只是个记号,其运算结果为 q(一般要求 0<q<|m|),仍为整数。
需要注意的是:当 $gcd(p, m) != 1$ 时,p 关于 m 的模逆不存在。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-3-19 21:06:14 | 显示全部楼层
算了,我就不去尝试了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-6-29 14:04:09 | 显示全部楼层
1# gxqcn

b^(2^(n-1))≡1 (mod 2^n)
x≡b^(2^(n-1)-1)(mod 2^n)

似乎不用迭代吧?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 19:17 , Processed in 0.045676 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表