Bob Bob - 20 days ago 7
Java Question

Leading zero in BigInteger multiplication

I use simple function to multiply big integers. Sometimes one more leading zero byte is included to output. Why is it happened and how I can prevent it?

PS: a and b are already less than mod

private byte[] multiply(final byte[] a, final byte[] b, final BigInteger mod) {
BigInteger M1 = new BigInteger(1, a);
BigInteger M2 = new BigInteger(1, b);

BigInteger out = M1.multiply(M2).mod(mod);

res = out.toByteArray();
}

Answer

The extra zero byte is added if the (positive) value has a first byte that is from 128 to 255.

This byte is needed so that the resulting byte are has at least one sign bit (https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#toByteArray%28%29)

BigInteger.valueOf(5L).toByteArray()

returns a byte array with only one byte (5).

BigInteger.valueOf(128L).toByteArray()

returns a byte array with only two bytes (0 and 128 in unsigned representation). This is to distinguish the result from

BigInteger.valueOf(-128L).toByteArray()

which returns also a byte array with two bytes (255, 128 in unsigned representation)