Modular reduction of large numbers
For a toy program, I need an efficient way to calculate
(2**64 * x) % m
where x
and m
are java long
, and **
denotes the exponent. This could be computed as
BigInteger.valueOf(x).shiftLeft(64).mod(BigInteger.valueOf(m)).longValue()
or by repeatedly switching x
left and decreasing, but both are quite slow. This is not a premature optimization.
Clarifications
‣ Any algorithm using BigInteger
is likely to be slower than the above expression.
‣ You may assume that it is m
too big for int
otherwise
long n = (1L<<32) % m;
return ((n*n) % m) * (x % m)) % m
...
‣ The slow shift and shrink algorithm is similar to
// assuming x >= 0
long shift32Left(long x, long m) {
long result = x % m;
for (int i=0; i<64; ++i) {
x <<= 1;
// here, `x<0` handles overflow
if (x<0 || x>=m) {
x -= m;
}
}
}
source to share
General form:
(a1 * a2 * a3 ... * an) % m = [(a1 % m) * (a2 % m) * ... * (a3 % m) ] % m
Apply the formula above:
(2^64 * x) % m = (((2^64) % m) * (x % m)) % m
For the first part: 2^64 mod m
. I can make a more general case 2^t mod m
. I have this pseudocode. In will work at N(log t)
times. This pseudocode for t and m only is a normal integer. Based on the range of t and m, you can correct the computation of the inner function to use BigInteger at a suitable point.
long solve(long t, long m) {
if (t == 0) return 1 % m;
if (t == 1) return t % m;
long res = solve(t/2, m);
res = (res * res) % m;
if (t % 2 == 1) res = (res * 2) % m;
return res;
}
Thanks for OldCurmudgeon. There can be one simple line above the code:
BigInteger res = (new BigInteger("2")).
modPow(new BigInteger("64"), new BigInteger("" + m));
Here is the implementation modPow
. This implementation takes different approaches. The algorithm starts with m: splits m into m = 2^k*q
. Then find modulo 2 ^ k and q, then use Chinese Reminder theorem
to compile the result.
public BigInteger modPow(BigInteger exponent, BigInteger m) {
if (m.signum <= 0)
throw new ArithmeticException("BigInteger: modulus not positive");
// Trivial cases
if (exponent.signum == 0)
return (m.equals(ONE) ? ZERO : ONE);
if (this.equals(ONE))
return (m.equals(ONE) ? ZERO : ONE);
if (this.equals(ZERO) && exponent.signum >= 0)
return ZERO;
if (this.equals(negConst[1]) && (!exponent.testBit(0)))
return (m.equals(ONE) ? ZERO : ONE);
boolean invertResult;
if ((invertResult = (exponent.signum < 0)))
exponent = exponent.negate();
BigInteger base = (this.signum < 0 || this.compareTo(m) >= 0
? this.mod(m) : this);
BigInteger result;
if (m.testBit(0)) { // odd modulus
result = base.oddModPow(exponent, m);
} else {
/*
* Even modulus. Tear it into an "odd part" (m1) and power of two
* (m2), exponentiate mod m1, manually exponentiate mod m2, and
* use Chinese Remainder Theorem to combine results.
*/
// Tear m apart into odd part (m1) and power of 2 (m2)
int p = m.getLowestSetBit(); // Max pow of 2 that divides m
BigInteger m1 = m.shiftRight(p); // m/2**p
BigInteger m2 = ONE.shiftLeft(p); // 2**p
// Calculate new base from m1
BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
? this.mod(m1) : this);
// Caculate (base ** exponent) mod m1.
BigInteger a1 = (m1.equals(ONE) ? ZERO :
base2.oddModPow(exponent, m1));
// Calculate (this ** exponent) mod m2
BigInteger a2 = base.modPow2(exponent, p);
// Combine results using Chinese Remainder Theorem
BigInteger y1 = m2.modInverse(m1);
BigInteger y2 = m1.modInverse(m2);
if (m.mag.length < MAX_MAG_LENGTH / 2) {
result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m);
} else {
MutableBigInteger t1 = new MutableBigInteger();
new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1);
MutableBigInteger t2 = new MutableBigInteger();
new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2);
t1.add(t2);
MutableBigInteger q = new MutableBigInteger();
result = t1.divide(new MutableBigInteger(m), q).toBigInteger();
}
}
return (invertResult ? result.modInverse(m) : result);
}
For the second part: you can easily use BigInteger
or just normal calculation, depends on the range of x and m.
source to share