- #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!
"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!