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

[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 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!

 

[Mark44]

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, %

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.

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!