Practical question about modular multiplication

In summary, the conversation discusses the difficulties of calculating modular exponents, specifically the issue of dealing with large numbers and avoiding overflow. The conversation suggests using a bit array to handle the numbers and suggests reducing the numbers modulo m before adding them. It also mentions the use of a bignum library to handle arbitrary precision operations. The conversation concludes with the suggestion to test the program and see how fast it runs.
  • #1
CRGreathouse
Science Advisor
Homework Helper
2,844
0
OK, so I'm writing a program and I want to calculate modular exponents. The only hard part is the multiplications. It would be best if I could work with numbers where, at all intermediate stages, each number is less than 2^64. If I must create a bit array I suppose I'll do that, but this would cause a huge performance drain.

The problem: given x, y, and m, calculate N:
[tex]N\equiv xy\pmod{m}[/tex]

I may have a modulus as large as 2^63-1, so I started by splitting each of my numbers to be multiplied into two parts:

[tex]x=x_1\cdot2^{32}+x_2,\;\;0\le x_1<2^{31},\;0\le x_2<2^{32}[/tex]
[tex]y=y_1\cdot2^{32}+y_2,\;\;0\le y_1<2^{31},\;0\le y_2<2^{32}[/tex]

So we have

[tex]N\equiv2^{64}x_1y_1+2^{32}(x_1y_2+x_2y_1)+x_2y_2\pmod{m}[/tex]

So far, so good:

[tex]x_1y_1<2^{62}[/tex]
[tex]x_1y_2+x_2y_1<2^{64}[/tex]
[tex]x_2y_2<2^{64}[/tex]

All three intermediate numbers are a workable size, and the constant multiplications can be computed with shifts (it's convenient for binary computers to multiply by powers of 2).

Here's the trouble: How do I combine these without overflowing? Alternately, is there a different set of steps I could take to get to the same result?
 
Mathematics news on Phys.org
  • #2
Slightly off-topic: Assuming C/C++, does your compiler implement the
long long datatype as 128 bit? Which would alleviate some of your overflow issues. This comment is motivated by your "64 bit int" statement in another thread.

The 64 bit systems here have 128 bit long long datatypes...sorry if I'm off-topic.
 
  • #3
Why not reduce those 3 quantities mod m before you add them? Reduce the powers of 2 as well before multiplying.
 
  • #4
shmoe said:
Why not reduce those 3 quantities mod m before you add them? Reduce the powers of 2 as well before multiplying.

I reduce the three quantities, but it doesn't help. Define M(a,b) as the usual % (since LaTeX hates me):

[tex]M(a,b)\equiv a\pmod{b},\;\;0\le M(a,b)<b[/tex]

Then the best bounds I have for the reduced quantities:

[tex]M(x_1y_1,m)\le2^{62}-1[/tex]
[tex]M(x_1y_2+x_2y_1,m)\le2^{63}-2[/tex]
[tex]M(x_2y_2,m)\le2^{63}-2[/tex]

I can't multiply two numbers together if their product is at least [tex]2^{64}[/tex].

Now the powers of 2 I can reduce, but so far only in an inefficient way. I double the number and reduce modulo m 32 and 64 times. This takes 96 shifts and 96 (expensive!) modulo operations, plus loopng overhead.
 
Last edited:
  • #5
jim mcnamara said:
Slightly off-topic: Assuming C/C++, does your compiler implement the
long long datatype as 128 bit? Which would alleviate some of your overflow issues. This comment is motivated by your "64 bit int" statement in another thread.

The 64 bit systems here have 128 bit long long datatypes...sorry if I'm off-topic.

It's not off-topic at all; my question is very nearly equivilent to the question, "How do I implement a 128-bit integer using only signed and unsigned longs?". Sadly, my compiler has 64-bit long longs.
 
  • #6
CRGreathouse said:
It's not off-topic at all; my question is very nearly equivilent to the question, "How do I implement a 128-bit integer using only signed and unsigned longs?". Sadly, my compiler has 64-bit long longs.

You implement it with a bignum library, like GMP, which is an arbitrary precision library for real and integer operations. There is version for most systems, even Windows.

http://swox.com/gmp/ [Broken]
 
Last edited by a moderator:
  • #7
CRGreathouse said:
Then the best bounds I have for the reduced quantities:

[tex]M(x_1y_1,m)\le2^{62}-1[/tex]
[tex]M(x_1y_2+x_2y_1,m)\le2^{63}-2[/tex]
[tex]M(x_2y_2,m)\le2^{63}-2[/tex]

I can't multiply two numbers together if their product is at least [tex]2^{64}[/tex].

That's fine, you can add two numbers that are less than 2^63 then reduce modulo m, which is all you need after you've multiplied by 2 enough times.

CRGreathouse said:
Now the powers of 2 I can reduce, but so far only in an inefficient way. I double the number and reduce modulo m 32 and 64 times. This takes 96 shifts and 96 (expensive!) modulo operations, plus loopng overhead.

You won't need to reduce modulo m 64 times to multiply by 2^64. You only need to reduce when you get something that's one shift away from 'going over'. If m is 63 bits, you should get to shift twice on average before needing to reduce (assuming random input on each stage, not really true of course). If m is smaller, even less mods wil be needed.

How expensive is the mod operator? I would hope mod(x,y) is zippy if y is nearly the same size as x, so even if m is 63 bits and you have to mod frequently, the operation should be fast no?


there are multiple libraries for large number arithmetic, gmp as mentioned, or bigint. I don't do much computer work myself, most of the time I'll just use maple or pari/gp which can handle big numbers already (and even with the added overhead will still be much faster than I would probably take the time to code).
 
  • #8
shmoe said:
How expensive is the mod operator? I would hope mod(x,y) is zippy if y is nearly the same size as x, so even if m is 63 bits and you have to mod frequently, the operation should be fast no?

The mod operator takes maybe 6 times longer than an addition or subtraction. You're right, though; there's no reason to use it when I can just check the bounds each time and subtract (once) if needed. This does bring it down a bit. I don't know how costly this frequent branching would be (hyperpipelined processors don't like conditional commands), but it would surely be faster.

OK, thanks, I'm going to try to write this program up and see how fast it is.
 

1. What is modular multiplication?

Modular multiplication is a mathematical operation that involves finding the remainder when two numbers are multiplied and divided by a third number, known as the modulus.

2. What are the practical applications of modular multiplication?

Modular multiplication is commonly used in cryptography, computer science, and coding theory. It is also used in various engineering fields for error correction and data transmission.

3. How is modular multiplication different from regular multiplication?

The main difference between modular multiplication and regular multiplication is that in modular multiplication, the result is always reduced to the remainder when divided by the modulus, whereas regular multiplication gives the exact product of the two numbers.

4. What is the significance of choosing a specific modulus in modular multiplication?

The choice of modulus in modular multiplication affects the outcome of the operation. Different moduli can result in different remainders and can impact the overall security and efficiency of the operation.

5. Are there any drawbacks to using modular multiplication?

One potential drawback of modular multiplication is that it can be computationally expensive for large numbers. Additionally, if the modulus is not carefully chosen, it can result in weak security for cryptographic applications.

Similar threads

Replies
3
Views
576
Replies
8
Views
1K
  • General Math
Replies
1
Views
2K
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
17
Views
1K
  • Topology and Analysis
Replies
2
Views
1K
Replies
36
Views
6K
  • Linear and Abstract Algebra
Replies
34
Views
1K
Replies
3
Views
1K
Replies
2
Views
1K
Back
Top