Modular Multiplication: How to Efficiently Calculate (a * b) mod c in C/C++?

In summary, the conversation discusses the need to manipulate three 64-bit numbers using the "a * b mod c" operation in a C/C++ program. The speaker asks for a well-known, efficient, and simple algorithm to implement this, but only knows how to calculate it using the modulus operator. They also express concern about overflow if the numbers are larger than 32 bits and mention that classes like BigInt and gmp cannot be used for this calculation.
  • #1
chesschi
3
0
I want to write a C/C++ program and encounter a problem.If I have three 64 bit numbers and need to manipulate
"a * b mod c"

Is there any well-known, efficient and simple algorithm to implement it?

I only know it can be calculated sth. like this..
__int64 a, b, c
a = x1 * 2^32 + x0
b = y1 * 2^32 + y0

then a * b = x1y1 * 2^64 + (x0y1 + x1y0) * 2^32 + x0y0

but I don't know what to do in the next step

Note that this cannot be calculated using some classes like BigInt, gmp

Thank you very much!
 
Mathematics news on Phys.org
  • #2
chesschi said:
I want to write a C/C++ program and encounter a problem.If I have three 64 bit numbers and need to manipulate
"a * b mod c"

Is there any well-known, efficient and simple algorithm to implement it?

I only know it can be calculated sth. like this..
__int64 a, b, c
a = x1 * 2^32 + x0
b = y1 * 2^32 + y0
C, C++, C#, and other languages that are based on C have a modulus operator, %

C:
unsigned long long a, b, c;
// Assign values to a, b, and c
x =  a * b % c;
One thing to be concerned about is that if a and b are larger than 32 bits, their product won't fit in 64 bits, and you'll get overflow.
chesschi said:
then a * b = x1y1 * 2^64 + (x0y1 + x1y0) * 2^32 + x0y0

but I don't know what to do in the next step

Note that this cannot be calculated using some classes like BigInt, gmp

Thank you very much!
 

1. What is modular multiplication?

Modular multiplication is a mathematical operation that involves multiplying two numbers and then taking the remainder when dividing by a third number called the modulus. It is often used in cryptography and computer science.

2. How is modular multiplication different from regular multiplication?

Modular multiplication differs from regular multiplication in that it takes the remainder of the result when divided by a third number. This makes it useful for working with large numbers and for certain applications where the exact value is not as important as the remainder.

3. What are some real-world applications of modular multiplication?

Modular multiplication is used in many areas, including cryptography for encrypting and decrypting data, computer graphics for creating patterns and textures, and error correction in communication systems. It is also used in some voting systems and in generating random numbers.

4. How is modular multiplication calculated?

To calculate modular multiplication, first perform regular multiplication of the two numbers. Then, divide the result by the modulus and take the remainder as the final answer. For example, to calculate 23 x 12 (mod 7), we would first multiply 23 by 12 to get 276. Then, we divide 276 by 7 and take the remainder, which is 6. So, 23 x 12 (mod 7) = 6.

5. Are there any drawbacks to using modular multiplication?

One drawback of modular multiplication is that it can lead to loss of information, as the remainder only gives a partial representation of the original numbers. Additionally, some calculations may become more complex when using modular multiplication compared to regular multiplication. However, for certain applications, such as cryptography, these drawbacks may be outweighed by the benefits of using modular multiplication.

Similar threads

  • Programming and Computer Science
Replies
14
Views
6K
  • Computing and Technology
Replies
11
Views
2K
  • Programming and Computer Science
Replies
14
Views
4K
  • Calculus and Beyond Homework Help
Replies
2
Views
3K
  • STEM Academic Advising
Replies
13
Views
2K
Back
Top