• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Efficient modular multiplication

 
Geoffrey Falk
Ranch Hand
Posts: 171
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Campbell Ritchie
Sheriff
Pie
Posts: 50184
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 171
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12196
35
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Jayesh A Lalwani
Rancher
Posts: 2756
32
Eclipse IDE Spring Tomcat Server
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 187
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4181
22
IntelliJ IDE Java Python
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Paul Clapham
Sheriff
Posts: 21416
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Posts: 21416
33
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic