## Modular computation of the matrix product

We conclude this chapter with another modular algorithm. We assume that we have a highly efficient matrix multiplication over , for any machine-word size prime number , and would like to take advantage of it for multipying matrcies with integer coefficients. This can be achieved by means of a modular algorithm, based on the Chinese Remaindering Algorithm.

Consider two square matrices and of order with coefficients in . Let and be the maximum absolute value of a coefficient in and , respectively. Let be the matrix product and let be any odd integer (prime or not). For all , we have

 (137)

and thus

 (138)

Now, let and be the images of and modulo . (Hence the coefficient of is the remainder of modulo .) Let be the matrix product computed in . Hence, we have

 (139)

Combining the relations

 (140)

with Equations (138) and (139) we obtain

 (141)

In particular, if we use a symmetric representation for representing the elements of and if we have , then Equation (141) simply becomes .

Observe that for all , we have

 (142)

Hence we define . We are ready to state a modular algorithm.

Algorithm 6

Note that the first for loop computes the matrcies by the classical method. However, one can use instead any other algorithm (like Strassen's) computing these matrices. Let us give an upper bound for the number of machine-word operations required by Algorithm 6. It suffices to estimate each of the two for loops. The first one runs in and the second one in . This is a better estimate than the one which can be given for the naive (non-modular approach): .

Marc Moreno Maza
2008-01-07