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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Practical question about modular multiplication

**Physics Forums | Science Articles, Homework Help, Discussion**