aspose file tools*
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: 36499
    
  16
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: 10916
    
  12

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: 2052
    
  22

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: 3948
    
  17

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: 18127
    
    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: 18127
    
    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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Efficient modular multiplication
 
Similar Threads
Primefaces Collector
Trying to get manageable arrays to work with
How to do export and import DB in mysql?
display needed in same line.
Jboss 5.1 Jndi related problem