#### Formulas.

Let and be two relatively prime elements of an Euclidean domain . (You may think or .) Let be such that . For every there exists such that

 (1)

where a convenient is given by

 (2)

Let and be two square matrices of order and with coefficients in where is a power of . We recall the Strassen's trick for computing .
If the matrices et are of the form et where , such that equals .
If the matrices and can be decomposed as

where and are square matrices of order . Then, one computes the following 8 sums.

Next, one computes the following 7 matrix products by recursive calls to the algorithm.

Finally, one computes the following 7 sums:

and one returns:

Next, we recall the Extended Euclidean Algorithm.

Marc Moreno Maza
2008-01-31