# Modular Multiplication

#### chesschi

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 dunno what to do in the next step

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

Thank you very much!!!

#### Mark44

Mentor
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 dunno what to do in the next step

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

Thank you very much!!!