Modular Multiplication

  • Thread starter chesschi
  • Start date
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 dunno what to do in the next step

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

Thank you very much!!!
 
32,830
4,545
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!!!
 

Want to reply to this thread?

"Modular Multiplication" You must log in or register to reply here.

Related Threads for: Modular Multiplication

Replies
7
Views
2K
  • Posted
Replies
7
Views
3K
  • Posted
Replies
4
Views
1K
  • Posted
Replies
5
Views
2K
  • Posted
Replies
8
Views
5K
  • Posted
Replies
6
Views
495
  • Posted
Replies
4
Views
2K
  • Posted
Replies
1
Views
1K
Top