montgomery乘法

无心人

考虑正奇数$n$，设$r=2^s$，$2^{s-1} <= n < 2^s$
则$(n, r) = 1$
且设$r^-1$为$r$模$n$的逆，同样$n^-1$为n模r的逆
定义$n' = -n^-1 (mod r) \quad m = t*n' (mod r)$
    对整数$t$成立

        $(t + m * n) // r -= t * r^-1 (mod n)$

注意同余式的左面，取模$r$同于并且做除$r$的除法，它为模$n$的一个余数。通过选择$r$为$2$的幂，即为$2^s$，可以简单的把$x$从第$s$比特分开而得到$x$模$r$的约化，可以通过$x$向右移动$s$比特来执行除法$r$除以$x$。

这一计算模$n$约化的原理称为montgomery约化。

为应用montgomery约化，利用合适的$r=2^s$将模$n$的计算转换到完全剩余系

    $R = R(r, n) = { i * r mod n | 0 <= i < n}$

然后定义$R$中的值$a$和$b$的montgomery乘积$xx$
   
   $a xx b = a * b * r^-1 mod n$

在$R(r, n)$中montgomery乘积$a xx b$算法
1、置$t = a * b$
2、置$m = t * n' (mod r)$
3、置$u = (t + m * n) // r$
4、若$u >= n$， 输出$u - n$，否则输出$n$

该算法使用了三个长乘法

用montgomery乘积计算$p = a * b (mod n)$， $n$为奇数
1、确定$r = 2^s, 2^{s-1} <=  n < 2^s$，用扩展的Euclid算法计算$1 = r'*r - n' * n$
2、置$a' = a*r (mod n)$
3、置$p = a xx b$并输出$p$

通常在算法里$mod n$运算， $n$是不变的，所以通过预先计算，模$n$的除法就转化为乘法运算了
而通常乘法是远超过除法速度的。

无心人

GxQ实现过这个算法么？
谈下感受

gxqcn

素性检测算法中少不了大量的模幂过程，所以模幂算法的效率至关重要。

在网上都比较推崇 Montgomery 算法，所以后来就自学了，并实现了它。
据我的实践，在数值较大时速度不理想，与 GMP 的代码表现一致：
在 GMP 中专门有一个临界值 POWM_THRESHOLD，只有小于它且模为奇数时才采用该算法。

这里顺带上传几个相关文档，供大家参考：

无心人

是不是如果当大于阀值
即使是素性测试算法也得不到好处？

mathematica

3# gxqcn


真是的,原来你都能看到GMP的算法的代码,然后用你的hugecalc与GMP比较快慢,
要是GMP也能看到你的代码,估计就不会比你慢了

inmen

gxqcn 发表于 2008-4-21 20:10
素性检测算法中少不了大量的模幂过程，所以模幂算法的效率至关重要。

在网上都比较推崇 Montgomery 算法 ...

附件过期了。。。

gxqcn

论坛之前用的是免费空间（最近已转成收费空间），
由于种种原因，先前的附件有部分缺失，很遗憾。

mathe

数值大的时候为什么效率会不好呢？乘法毕竟比除法快很多。是不是你模幂时指数不够大？我们应该选指数和模差不多大小的。实际是这算法在有限域上特别有用