cwave.eu5.org
Also see: http://www.angelfire.com/dragon/letstry
cwave04 at yahoo dot com
Free Guestbook
My Guestbook

Last updated on Fri May 21 11:50:24 IST 2010.

Modular multiplication (contd.)

We shall start with an example: 2367 times 3214 modulo 6345. Since the multipliers are not powers of small numbers, we shall start by computing the product explicitly:

and then compute the modulo. We already know that the trouble with this method is that the product may be too large to handle.

To avoid this we can reduce each of the intermediate results modulo 6345. The steps are: 

2367 * 4 = 9468  
2367 * 1 * 101 =  2367 * 101
2367 * 2 * 102 =  4734 * 102
2367 * 3 * 103 =  7101 * 103
At the end of each step we have a number multiplied by a power of 10. So we can reduce the product using the technique we have learned in the last page. Suppose that we have a C function modMultByPow10 for this modulo reduction (just like the modMultByPow2 that we actually wrote). Then we can write the above steps as 

modMultByPow10(2367 * 4,6345)  
modMultByPow10(2367 * 1,6345)
modMultByPow10(2367 * 2,6345)
modMultByPow10(2367 * 3,6345)
Now let us write these steps for multiplying a * b (mod m) where the digits of b are bk-1, bk-2, ... b1, b0. For example, when b=3214 we have k=4 and b3 = 3, b2 = 2, b1 = 1, b0 = 4. With this notation the steps are 

modMultByPow10(a * b0, 0, m)
...
modMultByPow10(a * bk-1, k-1, m)
We can add the results of these steps in a single for-loop in C: 

sum = 0;
for(i=0;i<k;i++) {
  sum = sum + modMultByPow10(a * bi, i, m);
}
Of course, this is still not a valid C code, since we do not yet know how to find the i-th digit bi in C. We shall learn that in a minute, but first notice that there is a possibility that the sum might become large after some steps. So it would be a good idea to reduce the sum modulo m after each step: 

sum = 0;
for(i=0;i<k;i++) {
  sum = sum + modMultByPow10(a * bi, i, m);
  sum = sum % m;
}
The multiplication a * bi at each step is very easy since each bi is a single digit, and so between 0 and 9. It becomes even easier if we work in binary, because a binary digit (or bit) can be either 0 or 1. If bi=0, then we basically skip the i-th step, otherwise the product is just a. 

sum = 0;
for(i=0;i<k;i++) {
  if(bi==1) {
    sum = sum + modMultByPow2(a, i, m);
    sum = sum % m;
  }
}
Notice that now we are using modMultByPow2 instead of modMultByPow10. So we have almost finished the C program, except that we still do not know how to find the bits, bi.

Finding bits in a number

C has a binary operator called bitwise and which is denoted by the symbol &. To compute 34 & 7 we first write down the two numbers in binary: 

37 = 100101
 7 =    111
Now add extra 0's (if needed) to the left of the smaller number to make both the representations of the same length: 

37 = 100101
 7 = 000111
Now perform a logical AND operation on each pair of bit. 

37 = 100101
 7 = 000111  

ans= 000101 = 5
Thus, the answer has a 1 in some bit iff both the operands have 1's in that bit. <hr>
A calculator for bitwise and
Type two numbers in the two boxes in the lhs, and click "=".
&
If the 1's in the the operanrds are in disjoint positions then the result is 0. For example 

41 = 101001
 6 = 000110

ans= 000000
We shall use the & operator to find the bits in a number as follows. Let the number be b. We shall create a another number called a mask that has exactly a single bit that is 1 (the remaining bits being 0). For example, the following numbers are all valid 4-bit masks: 

1000
0001
0100
Clearly, the masks are the powers of 2. The mask 2i has a 1 only in the i-th bit.

Thus the i-th bit of b is 1 iff b & 2i is non-zero (need not be 1, why?). Check this out using the calculator above.

C allows a handy notation for writing 2i. We just write 1<<i. This basically means
  1. write down a 1, which has a single 1-bit in the rightmost position.
  2. then move the 1-bit i places to the left.

Back to modular multiplication

Recall that we had the incomplete program: 

sum = 0;
for(i=0;i<k;i++) {
  if(bi==1) {
    sum = sum + modMultByPow2(a, i, m);
    sum = sum % m;
  }
}
We did not know how to check bi==1. Now we shall use & for this: 

sum = 0;
for(i=0;i<k;i++) {
  if((b & (1<<i)) != 0) {
    sum = sum + modMultByPow2(a, i, m);
    sum = sum % m;
  }
}
The != means "not equal to".

What k should we take? The number k is the number of bits in b. How do we know that? Well, in C unsigned int numbers are stored using 32 bits (usually). So we shall take k=32.

Combining all these we have a function for modular multiplication (notice how small it is!): 

unsigned int modMult(unsigned int a, unsigned int b, unsigned int m) {

  unsigned int sum = 0;
  for(i=0;i<32;i++) {
    if((b & (1<<i)) != 0) {
      sum = sum + modMultByPow2(a, i, m);
      sum = sum % m;
    }
  }
  return sum;
}
Testing
Here is a complete C program for testing. 

#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;
}

unsigned int modMult(unsigned int a, unsigned int b, unsigned int m) {

  unsigned int sum = 0;
  for(i=0;i<32;i++) {
    if((b & (1<<i)) != 0) {
      sum = sum + modMultByPow2(a, i, m);
      sum = sum % m;
    }
  }
  return sum;
}


main() {
  unsigned int y;

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

Where do we stand?

We have learned how to multiply two numbers modulo a third number. Since our technique does not require us to explicitly form the raw product, we can handle really large numbers using this algorithm.

This algorithm is one of the core algorithms in cryptography. We shall learn next how to use the modMult function to perform modulo exponentiation, i.e., computing ab (mod m) for given a,b and m.
PrevNext
© Arnab Chakraborty (2010)