Modular multiplication in different bases not working

change-of-basismodular arithmetic

I a working on a program in which I need to speed up a modular multiplication of two large numbers($a,b$). The code given to me has the number base $2^8$. Now I transformed this number to base $2^{16}$, and am trying to do the multiplication modulo $p$ where $p=2^{130}-5$.

Since this is too large to show an example I chose for p = $2^{24}-3$ in the example.
$a=0$x$eeabcb$ and $b=0$x$8e2539$, then the multiplication is as follows in base $2^8$:

               ee      ab      cb
               8e      25      39
              _____________________x
              34fe    2613    2d33
       2266   18b7    1d57
8404   5eda   709a
___________________________________
8485    fe     92      97      33

Then the reduction step would be as follows $0$x$fe929733+0$x$8485*3 \equiv 0$x$220292d\equiv0$x$20292d+2*3\equiv0$x$202933$

To do this a bit fast it is in handled in the code a bit differently, it takes the values that are larger than $2^{24}$ and multiplies it by 3, which comes from $2^{24} \equiv 3 mod 2^{24}-3$. The multiplication table then looks as follows:

       ee      ab      cb
       8e      25      39
      _____________________x
      34fe    2613    2d33
      18b7    1d57   11c8e
      709a   18c0c    6732
   ________________________
      c020      26      f3

Which is then reduce as before $0$x$2026f3+0$x$c0*3\equiv0$x$202933$

When I try doing this for $2^{16}$ I get the following:

           ee      abcb
           8e      2539
          ______________x
        229afe  18fa9733
8404    5f4a9a
________________________
8485      fe92     9733

This is still correct when the reduction is applied. However when I try to apply the same trick as before where values larger than $2^{24}$ are multiplied, then I do not get the same result.

           ee      abcb
           8e      2539
          ______________x
        229afe  18fa9733
        5f4a9a    18d8f
________________________
        81fe94     24c2

Then the reduction is as follows $0$x$9424c2+0$x$81fe*3 \equiv 0$x$95aabc$.
Why doesn't this work in base $2^{16}$ even though modular multiplication is possible in all bases.

Best Answer

I figured out why the answer wasn't correct. The 8404 from the base $2^{16}$ multiplication shouldn't be multiplied by $3$, but by $2^{32} \equiv 0x300 mod 2^{24}-3$. The multiplication will then look as follows:

           ee      abcb
           8e      2539
          ______________x
        229afe  18fa9733
        5f4a9a   18c0c00
________________________
        82001e    a333

Which after reduction gives the correct answer $0$x$8200*3+0$x$1ea333 = 0$x$202933$

So it is important to check with what you should multiply the number by.

Related Question