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

gxqcn

与普通的求模逆不同，这里的“模”本身是个 perfect power 即：已知正整数 n 及 b（b为奇数）， 求：整数x，使得 bx≡1 (mod 2^n) 由于模的特殊性，不知可有什么特别的快速算法？

gxqcn

现有一个比较好的递归算法，与大家分享一下： 若：$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)~|$ 次）。 但每次迭代需要两次大数乘法，可否有更适合大数运算的算法？

gxqcn

我自己又发现了一种更便于无符号系统实现的快速模幂算法， 不知谁有兴趣一同来探讨？

无心人

借我一个alpha64位工作站 我和你讨论

gxqcn

在 2#，给出了一个递归的算法。 其实对于某些特殊的底数，还有更快捷的算法。 比如求 PowMod( 4294770689, -1, 4294967296 ) ？ 其中 4294967296 = 2³²，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)$）， 运用上述定理求模逆相当高效。

wayne

若：m|(p-1)^2，则 p^(-1)≡m+2-p (modm) 我看不明白，p^(-1)还是整数吗

无心人

是，就是找个整数q 使得p * q = 1 (mod m)

gxqcn

对，p^(-1) 只是个记号，其运算结果为 q（一般要求 0

wayne

算了，我就不去尝试了

liushengqi000

1# gxqcn b^(2^(n-1))≡1 (mod 2^n) x≡b^(2^(n-1)-1)(mod 2^n) 似乎不用迭代吧？