gxqcn 发表于 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 http://bbs.emath.ac.cn/images/common/back.gif

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

打个比方，当 n=2^20 时（假定 b 与 m=2^n 相当），用你的方法每次得算两个n bit的大数乘法，
而我要说的算法则是倍增的算法：比如最后一次是 2^20 bit的大数乘法，前面一次则仅需 2^19 bit的大数乘法。

qianyb 发表于 2010-6-29 17:33:12

x不一定是符合的

570193465 发表于 2011-4-22 11:39:24

求解

G-Spider 发表于 2013-6-2 23:23:57

2# gxqcn
gmp中的binvert_limb用到这个方法。

gxqcn 发表于 2013-6-4 07:47:45

刚去下载了最新版的GMP，发现宏 binvert_limb 里的算法确实与 2# 的一致。
页: 1 [2]
查看完整版本: 快速求大整数关于 2^n 的模逆