Formulas.

Let $m$ and $n$ be two relatively prime elements of an Euclidean domain $R$ . (You may think $R = {\mbox{${\mathbb{Z}}$}}$ or $R = {\mbox{${\mathbb{Q}}$}}[x]$ .) Let $s, t \in R$ be such that $s \, m + t \, n = 1$ . For every $a, b \in R$ there exists $c \in R$ such that

$$(\forall x \in R) \ \ \ \ \ \left\{ \begin{array}{l} x \equiv a \... ...uiv b \mod{\, n} \\ \end{array} \right. \ \ \iff \ \ x \equiv c \mod{\, m \, n}$$ (1)

where a convenient $c$ is given by

$$c \ = \ a + (b - a) \, s \, m = b + (a - b) t\, n$$ (2)

Let $A$ and $B$ be two square matrices of order $n$ and with coefficients in ${\mathbb{Q}}$ where $n$ is a power of $2$ . We recall the Strassen's trick for computing $A B$ .

$(1)$

If $n=1$ the matrices $A$ et $B$ are of the form $(a)$ et $(b)$ where $a, b \in {\mbox{${\mathbb{Z}}$}}$ , such that $A \, B$ equals $(a \, b)$ .

$(2)$

If $n > 1$ the matrices $A$ and $B$ can be decomposed as

$$A = \left( \begin{array}{cc} A_{11} & A_{12} \\ A_{21} & A... ...}{cc} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right),$$

where $A_{ij}$ and $B_{ij}$ are square matrices of order $n/2$ . Then, one computes the following 8 sums.

$$\begin{array}{ll} S_1 = A_{21} + A_{22} \ \ \ \ & T_1 = B_{1... ...S_4 = A_{12} - S_2 \ \ \ \ & T_4 = T_2 - B_{21} \\ \end{array}$$

$(3)$

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

$$\begin{array}{ll} P_1 = A_{11} \, B_{11} \ \ \ \ & P_5 = S_1... ... \ & P_7 = S_3 \, T_3 \\ P_4 = A_{22} \, T_4 & \\ \end{array}$$

$(4)$

Finally, one computes the following 7 sums:

$$\begin{array}{ll} U_1 = P_1 + P_2 \ \ \ \ & U_5 = U_4 + P_3 ... ...\ \ \ \ & U_7 = U_3 + P_5 \\ U_4 = U_2 + P_5 & \\ \end{array}$$

and one returns:

$$\left( \begin{array}{cc} U_1 & U_5 \\ U_6 & U_7 \\ \end{array}\right).$$

Next, we recall the Extended Euclidean Algorithm.