Efficient BigInteger multiplication modulo n in Java

Question

I can calculate the multiplication of two BigIntegers (say a and b) modulo n.

This can be done by:

a.multiply(b).mod(n);

However, assuming that a and b are of the same order of n, it implies that during the calculation, a new BigInteger is being calculated, and its length (in bytes) is ~ 2n.

I wonder whether there is more efficient implementation that I can use. Something like modMultiply that is implemented like modPow (which I believe does not calculate the power and then the modulo).

Answer 1

I can only think of

a.mod(n).multiply(b.mod(n)).mod(n)

and you seem already to be aware of this.

BigInteger has a toByteArray() but internally ints are used. hence n must be quite large to have an effect. Maybe in key generation cryptographic code there might be such work.

Furhtermore, if you think of short-cutting the multiplication, you'll get something like the following:

public static BigInteger multiply(BigInteger a, BigInteger b, int mod) {
    if (a.signum() == -1) {
        return multiply(a.negate(), b, mod).negate();
    }
    if (b.signum() == -1) {
        return multiply(a, b.negate(), mod).negate();
    }

    int n = (Integer.bitCount(mod - 1) + 7) / 8; // mod in bytes.
    byte[] aa = a.toByteArray(); // Highest byte at [0] !!
    int na = Math.min(n, aa.length); // Heuristic.
    byte[] bb = b.toByteArray();
    int nb = Math.min(n, bb.length); // Heuristic.
    byte[] prod = new byte[n];
    for (int ia = 0; ia < na; ++ia) {
        int m = ia + nb >= n ? n - ia - 1 : nb; // Heuristic.
        for (int ib = 0; ib < m; ++ib) {
            int p = (0xFF & aa[aa.length - 1 - ia]) * (0xFF & bb[bb.length - 1 - ib]);
            addByte(prod, ia + ib, p & 0xFF);
            if (ia + ib + 1 < n) {
                addByte(prod, ia + ib + 1, (p >> 8) & 0xFF);
            }
        }
    }
    // Still need to do an expensive mod:
    return new BigInteger(prod).mod(BigInteger.valueOf(mod));
}

private static void addByte(byte[] prod, int i, int value) {
    while (value != 0 && i < prod.length) {
        value += prod[prod.length - 1 - i] & 0xFF;
        prod[prod.length - 1 - i] = (byte) value;
        value >>= 8;
        ++i;
    }
}

That code does not look appetizing. BigInteger has the problem of exposing the internal value only as big-endian byte[] where the first byte is the most significant one.

Much better would be to have the digits in base N. That is not unimaginable: if N is a power of 2 some nice optimizations are feasible.

(BTW the code is untested - as it does not seem convincingly faster.)

Answer 2

First, the bad news: I couldn't find any existing Java libraries that provided this functionality.

• I couldn't find any pure-Java big integer libraries ... apart from java.math.BigInteger.

• There are Java / JNI wrappers for the GMP library, but GMP doesn't implement this either.

So what are your options?

• Maybe there is some pure-Java library that I missed.

• Maybe there some other native (C / C++) big integer library supports this operation ... though you may need to write your own JNI wrappers.

• You should be able to implement such a method for yourself, by copying the source code of java.math.BigInteger and adding an extra custom method. Alternatively, it looks like you could extend it.

---

Having said that, I'm not sure that there is a "substantially faster" algorithm for computing a * b mod n in Java, or any other language. (Apart from special cases; e.g. when n is a power of 2).

Specifically, the "Montgomery Reduction" approach wouldn't help for a single multiplication step. (The Wikipedia page says: "Because numbers have to be converted to and from a particular form suitable for performing the Montgomery step, a single modular multiplication performed using a Montgomery step is actually slightly less efficient than a "naive" one.")

So maybe the most effective way to speedup the computation would be to use the JNI wrappers for GMP.