Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Fast multiplication and subtraction modulo a prime

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.

The code looks like this:

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]));
    }
}

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

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?

like image 362
Yrlec Avatar asked Oct 27 '11 10:10

Yrlec


1 Answers

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

See Wolfram Alpha.

like image 103
Artefacto Avatar answered Oct 18 '22 06:10

Artefacto