快速乘法和减法模运算成素数 [英] Fast multiplication and subtraction modulo a prime

问题描述

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

I need to optimize some code where I multiply a vector of ints (32 bit) by a scalar modulo p (where p is the prime number (2^32)-5) and then subtract that vector from another vector modulo 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]));
    }
}

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

I'm using longs because Java doesn't support unsigned integers but both vectors are mod p so you can expect every number to be 0 <= x < (2^32)-5

有什么想法可以优化吗? mod p操作占用了大部分执行时间，因此优化此操作的一种方法可能会以某种方式在乘法后不执行modP，而仅在减法后执行.有关如何执行此操作的任何想法?

Any ideas to optimize this? The mod p operation is what's taking up most of the execution time so one way to optimize this could to somehow not do modP after the multiplication and only do it after the subtraction. Any ideas on how to do that?

推荐答案

使用2 ^ 32 = 5(mod p)这一事实，可以加快计算速度并完全避免除法.

It is possible to speed up calculation and avoid any division at all using the fact that 2^32 = 5 (mod p).

相乘和相减后，将结果分成低(x％2 ^ 32)和高(x/2 ^ 32)的部分.然后将hi部分乘以5，然后将其与低部分相加.然后再次重复此过程.如果结果大于p，则减去p.对于否定结果，请添加p.

After multiplication and subtraction, split the result to low (x%2^32) and hi (x / 2^32) parts. Then multiply the hi part to 5 and sum with the low part. Then repeat this procedure once more. If the result is greater than p, subtract p. For negative result, add p.

由于组合的乘法和减法可能会溢出，因此乘法的结果也应取p为模.但是上述过程中只有一个步骤就足够了:只需拆分，乘以5并相加即可.

Since combined multiplication and subtraction may overflow, the result of multiplication should be also taken modulo p. But only one step of the above procedure is enough: just split, multiply to 5, and add.

这篇关于快速乘法和减法模运算成素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！