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

Maybe this:

static BigInteger multiply(BigInteger c, BigInteger x)
{
    BigInteger sum = BigInteger.ZERO;
    BigInteger addOperand;
    for (int i=0; i < FIELD_ELEMENT_BIT_SIZE; i++)
    {
        if (c.testBit(i))
            addOperand = x;
        else
            addOperand = BigInteger.ZERO;

        sum = add(sum, addOperand);

        x = x.shiftRight(1);
    }

    return sum;
}

with the following helper functions:

static BigInteger add(BigInteger a, BigInteger b)
{
    return modOrder(a.add(b));
}

static BigInteger modOrder(BigInteger n)
{
    return n.remainder(FIELD_ORDER);
}

To be honest though, I'm not sure if this is really efficient at all since none of these operations are performed in-place.

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.

Answer 3

You can write a BigInteger multiplication as a standard long multiplication in a very large base -- for example, in base 2^32. It is fairly straightforward. If you want only the result modulo n, then it is advantageous to choose a base that is a factor of n or of which n is a factor. Then you can ignore all but one or a few of the lowest-order result (Big)digits as you perform the computation, saving space and maybe time.

That's most practical if you know n in advance, of course, but such pre-knowledge is not essential. It's especially nice if n is a power of two, and it's fairly messy if n is neither a power of 2 nor smaller than the maximum operand handled directly by the system's arithmetic unit, but all of those cases can be handled in principle.

If you must do this specifically with Java BigInteger instances, however, then be aware that any approach not provided by the BigInteger class itself will incur overhead for converting between internal and external representations.

Answer 4

You can use generic maths, like: (A*B) mod N = ((A mod N) * (B mod N)) mod N

It may be more CPU intensive, but one should choose between CPU and memory, right?

If we are talking about modular arithmetic then indeed Montgomery reduction may be what you need. Don't know any out of box solutions though.

Answer 5

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.)