In order to analyze Algorithms 2 and 3
we introduce the following matrices
![$\displaystyle R_0 = \left( \begin{array}{cc} s_0 & t_0 \\ s_1 & t_1 \end{array}...
... & - q_{i+1} u^{-1}_{i+1} \end{array} \right) \ \ {\rm for} \ \ 1 \leq i \leq k$](img94.png) |
(12) |
with coefficients in
.
Then, we define
![$\displaystyle R_i = Q_i \cdots Q_1 R_0 \ \ {\rm for} \ \ 1 \leq i \leq k.$](img95.png) |
(13) |
The following proposition collects some invariants of the
Extended Euclidean Algorithm.
Proposition 1
With the convention that
and
,
for
we have
-
,
-
,
-
,
-
and
,
-
,
-
,
-
,
- the matrices
and
are invertible;
and
,
-
,
-
.
Proof.
We prove
![$ (i)$](img99.png)
and
![$ (ii)$](img101.png)
by induction on
![$ i$](img67.png)
.
The case
![$ i = 0$](img124.png)
follows immediately from the definitions
of
![$ s_0, r_0, s_1, r_1$](img125.png)
and
![$ R_0$](img126.png)
.
We assume that
![$ (i)$](img99.png)
and
![$ (ii)$](img101.png)
hold for
![$ 0 \leq i < k$](img127.png)
.
By induction hypothesis, we have
![\begin{displaymath}\begin{array}{rcl} R_{i+1} \left( \begin{array}{c} a \\ b \en...
...n{array}{c} r_{i+1} \\ r_{i+2} \end{array} \right). \end{array}\end{displaymath}](img128.png) |
(14) |
Similarly, we have
![\begin{displaymath}\begin{array}{rcl} R_{i+1} & = & Q_{i+1} R_i \\ & = & Q_{i+1}...
...& t_{i+1} \\ s_{i+2} & t_{i+2} \end{array} \right). \end{array}\end{displaymath}](img129.png) |
(15) |
Property
![$ (iii)$](img103.png)
follows from our study of Algorithm
1.
Claim
![$ (iv)$](img105.png)
follows
![$ (i)$](img99.png)
and
![$ (ii)$](img101.png)
.
Taking the determinant of each side of
![$ (ii)$](img101.png)
we prove
![$ (v)$](img108.png)
as follows:
![\begin{displaymath}\begin{array}{rcl} s_i t_{i+1} - t_i s_{i+1} & = & {\rm det} ...
... (u_{i+1} \cdots u_2)^{-1} (u_0^{-1} u_1^{-1} - 0). \end{array}\end{displaymath}](img130.png) |
(16) |
Now, we prove
![$ (vi)$](img110.png)
.
If
![$ s_i$](img131.png)
and
![$ t_i$](img132.png)
would have a non-invertible common factor, then it would
divide
![$ s_i t_{i+1} - t_i s_{i+1}$](img133.png)
.
This contradicts
![$ (v)$](img108.png)
and proves
![$ (vi)$](img110.png)
.
We prove
![$ (vii)$](img112.png)
.
Let
![$ p \in R$](img134.png)
be a divisor of
![$ t_i$](img132.png)
.
If
![$ p \mid a$](img135.png)
, then
![$ p \mid r_i$](img136.png)
holds since we have
![$ r_i = s_i a + t_i b$](img137.png)
from
![$ (i)$](img99.png)
.
If
![$ p \mid r_i$](img136.png)
, then
![$ p \mid s_i a$](img138.png)
and, thus,
![$ p \mid a$](img135.png)
since
![$ t_i$](img132.png)
and
![$ s_i$](img131.png)
are relatively prime, from
![$ (vi)$](img110.png)
.
Therefore,
![$ (vii)$](img112.png)
holds.
We prove
![$ (viii)$](img114.png)
.
From
![$ (v)$](img108.png)
, we deduce that
![$ Q_i$](img116.png)
is invertible.
Then, the invertibility of
![$ R_i$](img115.png)
follows easily from that of
![$ Q_i$](img116.png)
.
It is routine to check that the proposed inverses are correct.
Finally, claims
![$ (ix)$](img119.png)
and
![$ (x)$](img121.png)
are derived from
![$ (i)$](img99.png)
by multiplying each side with the inverse of
![$ R_i$](img115.png)
given in
![$ (viii)$](img114.png)
.
In the case
where
is a field,
the following Proposition 2
shows that the degrees of
the Bézout coefficients of the
Extended Euclidean Algorithm grow linearly
whereas Proposition 3
shows that Bézout coefficients are essentially unique,
provided that their degrees are small enough.
Proof.
We only prove the first equality since the second one can be verified
in a similar way.
In fact, we prove this first equality together with
![$\displaystyle {\deg} s_{i-1} < {\deg} s_i$](img143.png) |
(19) |
by induction on
![$ 2 \leq i \leq k+1$](img139.png)
.
For
![$ i = 2$](img144.png)
, the first equality holds since we have
![$\displaystyle {\deg} s_i = {\deg} (s_0 - q_2 s_1) = {\deg} (1 - 0 \, q_2 ) = 0 = n_1 - n_{i-1}$](img145.png) |
(20) |
and the inequality holds since we have
![$\displaystyle - \infty = {\deg} s_1 < {\deg} s_2 = 0.$](img146.png) |
(21) |
Now we consider
![$ i \geq 2$](img147.png)
and we assume that both properties
hold for
![$ 2 \leq j \leq i$](img148.png)
.
Then, by induction hypothesis, we have
![$\displaystyle {\deg} s_{i-1} < {\deg} s_i < n_{i-1} - n_i + {\deg} s_i = {\deg} q_{i+1} + {\deg} s_i = {\deg} (q_{i+1} s_i)$](img149.png) |
(22) |
which implies
![$\displaystyle {\deg} s_{i+1} = {\deg} (s_{i-1} - q_{i+1} s_i) = {\deg} (q_{i+1} s_i) > {\deg} s_i$](img150.png) |
(23) |
and
![$\displaystyle {\deg} s_{i+1} = {deg} q_{i+1} + {\deg} s_i = {deg} q_{i+1} + {\sum}_{3 \leq j \leq i} {\deg} q_j = {\sum}_{3 \leq j \leq i+1} {\deg} q_j$](img151.png) |
(24) |
where we used the induction hypothesis also.
Proof.
First, we observe that the index
![$ j$](img160.png)
exists and is unique. Indeed,
we have
![$ - \infty < {\deg} r < n$](img161.png)
and,
![$\displaystyle - \infty = {\deg} r_{k+1} < {\deg} r_k < \cdots < {\deg} r_{i+1} < {\deg} r_{i} < \cdots < {\deg} a = n.$](img162.png) |
(28) |
Second, we claim that
![$\displaystyle s_j t = s t_j$](img163.png) |
(29) |
holds.
Suppose that the claim is false and consider the following linear
system over
![$ R$](img1.png)
with
![$ \left(\begin{array}{c} f \\ g \end{array}\right) $](img164.png)
as unknown:
![$\displaystyle \left( \begin{array}{cc} s_j & t_j \\ s & t \end{array} \right) \...
...\\ g \end{array} \right) = \left( \begin{array}{c} r_j \\ r \end{array} \right)$](img165.png) |
(30) |
Since the matrix of this linear system is non-singular, we can solve for
![$ f$](img166.png)
over the field of fractions of
![$ R$](img1.png)
.
Moreover, we know that
![$ \left(\begin{array}{c} f \\ g \end{array}\right) =
\left(\begin{array}{c} a \\ b \end{array}\right) $](img167.png)
is the solution.
Hence, using Cramer's rule we obtain:
![$\displaystyle a = \frac{ {\rm det} \left( \begin{array}{cc} r_j & t_j \\ r & t ...
...}{ {\rm det} \left( \begin{array}{cc} s_j & t_j \\ s & t \end{array} \right) }.$](img168.png) |
(31) |
The degree of the left hand side is
![$ n$](img169.png)
while the degree of the right hand side is equal or less than:
![\begin{displaymath}\begin{array}{rcl} {\deg}(r_j t -r t_j) & \leq & {\max} ({\de...
...n, {\deg} r_{j-1} + n - {\deg} r_{j-1}) \\ & = & n, \end{array}\end{displaymath}](img170.png) |
(32) |
by virtue of the definition of
![$ j$](img160.png)
, Relation (
25) and
Proposition
2.
This leads to a contradiction.
Hence, we have
![$ s_j t = s t_j$](img171.png)
.
This implies that
![$ t_j$](img172.png)
divides
![$ t s_j$](img173.png)
.
Since
![$ s_j$](img174.png)
and
![$ t_j$](img172.png)
are relatively prime (Point
![$ (vi)$](img110.png)
of Proposition
1) we deduce that
![$ t_j$](img172.png)
divides
![$ t$](img175.png)
.
So let
![$ {\alpha} \in {\bf k}[x]$](img158.png)
such that
we have
![$\displaystyle t = {\alpha} t_j.$](img176.png) |
(33) |
Hence we obtain
![$ s_j {\alpha} t_j = s t_j$](img177.png)
.
Since
![$ t \neq 0$](img154.png)
holds, we have
![$ t_j \neq 0$](img178.png)
, leading to
![$\displaystyle s = s_j {\alpha}.$](img179.png) |
(34) |
Finally, plugging Equation (
33) and Equation (
34)
in Equation (
25), we obtain
![$ r = {\alpha} r_j$](img180.png)
, as claimed.
Proposition 4
Let
where
is a field.
Assume
.
- Algorithm 3 requires at most
inversions and
additions
and multiplications in
.
- If we do not compute the coefficients
then
Algorithm 3 requires at most
inversions and
additions
and multiplications in
.
Proof.
See Theorem 3.11 in [
GG99].
Proposition 5
Let
be multi-precision integers written with
and
words.
Algorithm 3 can be performed in
word operations.
Proof.
See Theorem 3.13 in [
GG99].
Marc Moreno Maza
2008-01-07