快速求大整数关于 2^n 的模逆

gxqcn

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的大数乘法。

qianyb

x不一定是符合的

570193465

求解

G-Spider

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

gxqcn

刚去下载了最新版的GMP，发现宏 binvert_limb 里的算法确实与 2# 的一致。