- #1
- 2,844
- 0
OK, so I'm writing a program and I want to calculate modular exponents. The only hard part is the multiplications. It would be best if I could work with numbers where, at all intermediate stages, each number is less than 2^64. If I must create a bit array I suppose I'll do that, but this would cause a huge performance drain.
The problem: given x, y, and m, calculate N:
[tex]N\equiv xy\pmod{m}[/tex]
I may have a modulus as large as 2^63-1, so I started by splitting each of my numbers to be multiplied into two parts:
[tex]x=x_1\cdot2^{32}+x_2,\;\;0\le x_1<2^{31},\;0\le x_2<2^{32}[/tex]
[tex]y=y_1\cdot2^{32}+y_2,\;\;0\le y_1<2^{31},\;0\le y_2<2^{32}[/tex]
So we have
[tex]N\equiv2^{64}x_1y_1+2^{32}(x_1y_2+x_2y_1)+x_2y_2\pmod{m}[/tex]
So far, so good:
[tex]x_1y_1<2^{62}[/tex]
[tex]x_1y_2+x_2y_1<2^{64}[/tex]
[tex]x_2y_2<2^{64}[/tex]
All three intermediate numbers are a workable size, and the constant multiplications can be computed with shifts (it's convenient for binary computers to multiply by powers of 2).
Here's the trouble: How do I combine these without overflowing? Alternately, is there a different set of steps I could take to get to the same result?
The problem: given x, y, and m, calculate N:
[tex]N\equiv xy\pmod{m}[/tex]
I may have a modulus as large as 2^63-1, so I started by splitting each of my numbers to be multiplied into two parts:
[tex]x=x_1\cdot2^{32}+x_2,\;\;0\le x_1<2^{31},\;0\le x_2<2^{32}[/tex]
[tex]y=y_1\cdot2^{32}+y_2,\;\;0\le y_1<2^{31},\;0\le y_2<2^{32}[/tex]
So we have
[tex]N\equiv2^{64}x_1y_1+2^{32}(x_1y_2+x_2y_1)+x_2y_2\pmod{m}[/tex]
So far, so good:
[tex]x_1y_1<2^{62}[/tex]
[tex]x_1y_2+x_2y_1<2^{64}[/tex]
[tex]x_2y_2<2^{64}[/tex]
All three intermediate numbers are a workable size, and the constant multiplications can be computed with shifts (it's convenient for binary computers to multiply by powers of 2).
Here's the trouble: How do I combine these without overflowing? Alternately, is there a different set of steps I could take to get to the same result?