快速求大整数关于 2^n 的模逆
与普通的求模逆不同，这里的“模”本身是个 perfect power即：已知正整数 n 及 b（b为奇数），
求：整数x，使得 bx≡1 (mod 2^n)
由于模的特殊性，不知可有什么特别的快速算法？ 现有一个比较好的递归算法，与大家分享一下：
若：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)~| 次）。
但每次迭代需要两次大数乘法，可否有更适合大数运算的算法？ 我自己又发现了一种更便于无符号系统实现的快速模幂算法，
不知谁有兴趣一同来探讨？ :lol
借我一个alpha64位工作站
我和你讨论 在 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)$），
运用上述定理求模逆相当高效。 若：m|(p-1)^2，则 p^(-1)≡m+2-p(modm)
我看不明白，p^(-1)还是整数吗 是，就是找个整数q
使得p * q = 1 (mod m) 对，p^(-1) 只是个记号，其运算结果为 q（一般要求 0<q<|m|），仍为整数。
需要注意的是：当 $gcd(p, m) != 1$ 时，p 关于 m 的模逆不存在。 算了，我就不去尝试了 1# gxqcn
b^(2^(n-1))≡1 (mod 2^n)
x≡b^(2^(n-1)-1)(mod 2^n)
:)似乎不用迭代吧？
页:
[1]
2