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?
e - (f * e mod p) mod p = (e-e f) mod p
See Wolfram Alpha.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With