my dog learned polymorphism*
The moose likes Java in General and the fly likes Efficient modular multiplication Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Efficient modular multiplication" Watch "Efficient modular multiplication" New topic
Author

Efficient modular multiplication

Geoffrey Falk
Ranch Hand

Joined: Aug 17, 2001
Posts: 171
    
    1
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


Sun Certified Programmer for the Java 2 Platform
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38486
    
  23
How do you know it is taking too much space? How much space do yo have available? What algorithm would you suggest?
Geoffrey Falk
Ranch Hand

Joined: Aug 17, 2001
Posts: 171
    
    1
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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11256
    
  16

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.

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

Joined: Jan 17, 2008
Posts: 2342
    
  28

Yeah, Immutables are not good when you are doing large volume operations. That is one of the reasons why Java tells you to use StringBuffer/StringBuilder instead of String when you are dealing with large number of String operations.
Emanuel Kadziela
Ranch Hand

Joined: Mar 24, 2005
Posts: 186
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):


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
Steve Luke
Bartender

Joined: Jan 28, 2003
Posts: 4181
    
  21

Hi Emmanual,

Unfortunately, according to the original post:
BigIntegers A, B (that are between 0 and M-1)
. If A and B are < M-1, then rA == A, and rB == B, and you gain nothing from doing ((A mod M) (B mod M)) mod M.


Steve
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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.

Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 18541
    
    8

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.
 
Consider Paul's rocket mass heater.
 
subject: Efficient modular multiplication