快速乘法和减法模数为素数

Question

我需要优化一些代码,其中我将一个int(32位)的向量乘以标量模p(其中p是素数(2 ^ 32)-5),然后从另一个向量模p中减去该向量.

代码如下所示:

public static void multiplyAndSubtract(long fragmentCoefficient, long[] equationToSubtractFrom, long[] equationToSubtract) {
    for (int i = 0; i < equationToSubtractFrom.length; i++) {
        equationToSubtractFrom[i] =  modP(equationToSubtractFrom[i] - multiplyModP(fragmentCoefficient, equationToSubtract[i]));
    }
}

我使用longs因为Java不支持无符号整数但两个向量都是mod p所以你可以期望每个数字都是0 <= x <(2 ^ 32)-5

有什么想法来优化这个？mod p操作占用了大部分执行时间,因此优化这种方法的一种方法可能是在乘法后不知道怎么做modP并且只在减法后做.有关如何做到这一点的任何想法？

Answer 1

e - (f * e mod p) mod p = (e-e f) mod p

见Wolfram Alpha.

Answer 2

使用 2^32 = 5 (mod p) 的事实可以加速计算并避免任何除法。

乘法和减法后，将结果拆分为low (x%2^32) 和hi (x / 2^32) 部分。然后将高部分乘以 5 并与低部分相加。然后再次重复此过程。如果结果大于 p，则减去 p。对于阴性结果，添加 p。

编辑：由于组合乘法和减法可能会溢出，乘法的结果也应该取模 p。但上述过程只需一步就足够了：只需拆分，乘以 5，然后添加。