# Efficient modular multiplication

Geoffrey Falk

Ranch Hand

Posts: 171

1

posted 3 years ago

I have BigInteger M (a modulus) and two BigIntegers A, B (that are between 0 and M-1) that I would like to multiply together modulo M.

One way to do it is

The problem is, this uses twice as much space as it should need. I want to use an algorithm to do the modular multiplication in the same space as M.

BigInteger doesn't provide such a method, however.

What can I use?

Thanks

Geoffrey

One way to do it is

The problem is, this uses twice as much space as it should need. I want to use an algorithm to do the modular multiplication in the same space as M.

BigInteger doesn't provide such a method, however.

What can I use?

Thanks

Geoffrey

Sun Certified Programmer for the Java 2 Platform

Campbell Ritchie

Sheriff

Posts: 50184

79

Geoffrey Falk

Ranch Hand

Posts: 171

1

posted 3 years ago

The issue is garbage collection of the intermediate object A.multiply(B), which has size size(A) + size(B). If I am doing millions or billions of operations, this gets quite significant.

It would be much more convenient to have an algorithm to do the modular multiplication in place.

I suppose I will have to implement this myself.

It would be much more convenient to have an algorithm to do the modular multiplication in place.

I suppose I will have to implement this myself.

Sun Certified Programmer for the Java 2 Platform

posted 3 years ago

my advice would be to be careful.

it is possible your implementation would be more memory efficient, but less time efficient. If the built-in way runs in one microsecond, but yours takes one second, then time will become more important than memory.

I have no idea if this will actually be the case, but it is something to at least consider.

it is possible your implementation would be more memory efficient, but less time efficient. If the built-in way runs in one microsecond, but yours takes one second, then time will become more important than memory.

I have no idea if this will actually be the case, but it is something to at least consider.

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Emanuel Kadziela

Ranch Hand

Posts: 187

posted 3 years ago

So I did some googling and here's what I found (hope it helps - I believe it will, since AxB is a huge number, as you mentioned, but (A mod n)x(B mod n) should be much smaller):

Copied from http://www.dragonwins.com/domains/getteched/crypto/modular_arithmetic_intro.htm#Modular Multiplication

Modular Multiplication

A very similar development can be used to show that the modulo operator replicates over multiplication.

Given the expression

c = (ab) mod n

we could, of course, evaluate it directly. But we can also invoke the definition of a residue as follows:

a = kan + ra

b = kbn + rb

Where ka and kb are appropriate integers and ra and rb are the residues of a and b respectively. Hence

c = ( ( kan + ra )( kbn + rb) ) mod n

c = ( (kakb)n2 + (rakb + rbka)n + (rarb) ) mod n

We can then replicate the modulo operator over the sum of terms yielding

c = ( ((kakb)n2 mod n ) + ((rakb + rbka)n mod n) + ((rarb) mod n) ) mod n

Since the first two terms contain n as a factor their residues are zero, leaving

c = ( (rarb) mod n) ) mod n

The second modulo operation is redundant and can be removed.

c = (rarb) mod n

We also have, by definition,

ra = a mod n

rb = b mod n

Combining all of this, we get the following property of modular addition:

(ab) mod n = ((a mod n)(b mod n)) mod n

Copied from http://www.dragonwins.com/domains/getteched/crypto/modular_arithmetic_intro.htm#Modular Multiplication

posted 3 years ago

Right. To put Geoffrey's problem another way, A and B are 1-digit numbers in base M. So when you multiply them you get a 2-digit number, of which you only require the second digit. This is a potential problem for Geoffrey because M is a large number.

Unfortunately the technique posted by Emanuel starts by reducing A and B to their last digits in the base-M representation, which is the correct general solution but doesn't help in this particular case.

If you put M = 10 just for ease of thinking about the problem, it's asking (for example) how to calculate that 6 x 7 ends in 2 without having to evaluate 42 at any time in the calculation.

Unfortunately the technique posted by Emanuel starts by reducing A and B to their last digits in the base-M representation, which is the correct general solution but doesn't help in this particular case.

If you put M = 10 just for ease of thinking about the problem, it's asking (for example) how to calculate that 6 x 7 ends in 2 without having to evaluate 42 at any time in the calculation.

posted 3 years ago

One way to do that is to replace the multiplication by repeated addition, applying mod-M at each step. This means that the largest number you ever use in the calculation is of the order of 2M, rather than M^2. However as fred warned, this algorithm is likely to be much slower than the plain old multiply and reduce mod M algorithm. Not to mention that if the issue is garbage collection of temporary objects used in the calculation, this algorithm is likely to produce a lot more temporary objects which are somewhat smaller.

Paul Clapham wrote:If you put M = 10 just for ease of thinking about the problem, it's asking (for example) how to calculate that 6 x 7 ends in 2 without having to evaluate 42 at any time in the calculation.

One way to do that is to replace the multiplication by repeated addition, applying mod-M at each step. This means that the largest number you ever use in the calculation is of the order of 2M, rather than M^2. However as fred warned, this algorithm is likely to be much slower than the plain old multiply and reduce mod M algorithm. Not to mention that if the issue is garbage collection of temporary objects used in the calculation, this algorithm is likely to produce a lot more temporary objects which are somewhat smaller.