- #1

CRGreathouse

Science Advisor

Homework Helper

- 2,820

- 0

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?