找回密码
 欢迎注册
楼主: gxqcn

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

[复制链接]
 楼主| 发表于 2010-6-29 14:20:36 | 显示全部楼层
1# gxqcn

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

似乎不用迭代吧?
liushengqi000 发表于 2010-6-29 14:04


这样虽然直接,但效率并不高。

打个比方,当 n=2^20 时(假定 b 与 m=2^n 相当),用你的方法每次得算两个n bit的大数乘法,
而我要说的算法则是倍增的算法:比如最后一次是 2^20 bit的大数乘法,前面一次则仅需 2^19 bit的大数乘法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-6-29 17:33:12 | 显示全部楼层
x不一定是符合的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2011-4-22 11:39:24 | 显示全部楼层
求解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-6-2 23:23:57 | 显示全部楼层
2# gxqcn
gmp中的binvert_limb用到这个方法。

评分

参与人数 1经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-6-4 07:47:45 | 显示全部楼层
刚去下载了最新版的GMP,发现宏 binvert_limb 里的算法确实与 2# 的一致。

评分

参与人数 1经验 +6 鲜花 +6 收起 理由
wayne + 6 + 6

查看全部评分

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

本版积分规则

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

GMT+8, 2024-3-19 18:18 , Processed in 0.041664 second(s), 15 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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