Modular multiplication I

We shall learn here how to multiply two numbers a,b modulo a third number m. First, let us introduce a new notation. By a % m we shall understand the remainder of a when divided by m. So our aim here is to find (a*b) % m (where * denotes multiplication).

The simplest way to compute (a*b) % m is by first computing a*b and reducing it modulo m. But if a and b are already large numbers, a*b may be too large to compute.

So we need an indirect method that avoids computing a*b first.

If b=r^k where r is small...

...then we can form the product a*b step by step as a*r, a*r²,a*r³ etc, reducing modulo m after each step, so that the result never gets too large. Let us see an example


1234 times 7⁵ (mod 3245)
1234 * 7 =  8638 = 2148
1234 * 7² = 2148 * 7 = 15036 = 2056
1234 * 7³ = 2056 * 7 = 14392 = 1412
1234 * 7⁴ = 1412 * 7 = 9884 = 149
1234 * 7⁵ = 149 * 7 = 1043 = 1043

Here at each step we have to do two things: a multiplication by 7, and a reduction mod 3245. Convince yourself that the following C code does this:


x = x * 7
x = x % 3245

For example, if we start with x = 1234 then after these two lines we have x = 2148.

We can combine the two lines into a single line


x = ( x * 7 ) % 3245

We have to execute this line 5 times starting with x = 1234. Then finally x will have the required value 1043.


x = 1234;
for(i=0;i<5;i++) {
  x = ( x * 7 ) % 3245; 
}

The multiplication would have been very easy to do by hand if the multiplier were 10 instead of 7, as in the next example:


1234 * 10⁵ (mod 3245)
1234 * 10 = 12340 =  2605
1234 * 10² = 2605 * 10= 26050 = 90
1234 * 10³ = 90 * 10= 900 = 900
1234 * 10⁴ = 900 * 10= 9000 = 2510
1234 * 10⁵ =  2510 * 10 =  25100 = 2385

Here the green steps were all trivial, they involved just adding an extra 0 to the right. This is because we are using decimal system. In binary the same advantage can be had if we multiply a number by 2. For example, 5 = (101)₂ and 2*5 = (1010)₂. Adding a 0 at the end of the binary represetation of a number is done in C as (x<<1). It has the same effect as 2 * x except that it is faster. So if we want to compute


1234 *   2⁵ (mod 3245)

then we can use the following C code:


x = 1234;
for(i=0;i<5;i++) {
  x = ( x << 1 ) % 3245; 
}

This technique can be used to find a * 2^k (mod m) for any a, k and m. So we can write in general:


x = a;
for(i=0;i<k;i++) {
  x = ( x << 1 ) % m; 
}

By the way, it would be even better if we start by reducing a right at the beginning:


x = a % m;
for(i=0;i<k;i++) {
  x = ( x << 1 ) % m; 
}

Let us package it into a function for future use:


unsigned int modMultByPow2(unsigned int a, unsigned int k, unsigned int m) {
  int x, i;

  x = a % m;
  for(i=0;i<k;i++) {
    x = ( x << 1 ) % m; 
  }
return x;
}

By unsigned int we mean an integer that can take only nonnegative values.

If you have access to a computer with a C compiler then it will be a good idea to test this function now. For this you have write a main function that will call this multModPow2 function. An complete example program (ready to be compiled and executed) is like this:


#include <stdio.h>
unsigned int modMultByPow2(unsigned int a, unsigned int k, unsigned int m) {
  int x, i;

  x = a % m;
  for(i=0;i<k;i++) {
    x = ( x << 1 ) % m; 
  }

  return x;
}

main() {
  unsigned int y;

  y = modMultByPow2(23,4,123);
  printf("23 * 4 = %u mod 123.\n",y);
}

Here %u is a special symbol that is used to print unsigned int variables. This is like the %d used for printing int. The % in %u has nothing to do with modulo!

Where do we stand?

We have learned in this page how to perform modulo multiplication if one of the multipliers is a power of a smal number. In the special case when this small number is 2, we have seen how to write a C program to do the multiplication.

We shall use this function cleverly in the next page to do modulo multiplication even when the multipliers are not powers of small numbers.

Modular multiplication I