programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Tim Cooke
• Campbell Ritchie
• Ron McLeod
• Junilu Lacar
• Liutauras Vilda
Sheriffs:
• Paul Clapham
• Jeanne Boyarsky
• Henry Wong
Saloon Keepers:
• Tim Moores
• Tim Holloway
• Stephan van Hulst
• Piet Souris
• Carey Brown
Bartenders:
• Jesse Duncan
• Frits Walraven
• Mikalai Zaikin

# Efficient modular multiplication

Ranch Hand
Posts: 171
1
• Number of slices to send:
Optional 'thank-you' note:
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

Marshal
Posts: 75851
361
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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.

lowercase baba
Posts: 13056
67
• Number of slices to send:
Optional 'thank-you' note:
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.

Rancher
Posts: 2759
32
• Number of slices to send:
Optional 'thank-you' note:
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.

Ranch Hand
Posts: 187
• Number of slices to send:
Optional 'thank-you' note:
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

Bartender
Posts: 4179
22
• Number of slices to send:
Optional 'thank-you' note:
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.

Sheriff
Posts: 27235
87
• Number of slices to send:
Optional 'thank-you' note:
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: 27235
87
• Number of slices to send:
Optional 'thank-you' note:

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.

 pie. tiny ad: Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton