Euclidean algorithm and its applications

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 4, January 29 Scribe: Jennifer van der Horst

Today we restrict ourself to univariate polynomials and examine the Euclidean algorithm in details. Let ${\mathbb F}$ be any field (e.g. ${\mathbb F}_{2^n}, {\mathbb F}_{q}, {\mathbb Q}, {\mathbb C}, ...$). We consider the following problems:

Problem 4.1   Given $a(x), b(x) \in {\mathbb F}[x]$, decide if they have a nontrivial common divisor in ${\mathbb F}[x]$.

This is typically a nontrivial problem. An equivalent problem is to decide if a(x) and b(x) have a common zero in some extension field of ${\mathbb F}$.

Problem 4.2   Given $a(x), b(x), r(x) \in {\mathbb F}[x]$, decide if r(x) can be written as

r(x) = u(x)a(x) + v(x)b(x)

for some $u(x), v(x) \in {\mathbb F}[x]$.

Problem 4.3 (Rational Function Approximation of Polynomials)   : Given $a(x), b(x) \in {\mathbb F}[x]$, find $r(x), v(x) \in {\mathbb F}[x]$ such that

$$b(x) \equiv \frac{r(x)}{v(x)} \pmod{a(x)}.$$

For the above relationship, the degrees of r(x) and b(x) are often bounded in some way. This usually depends on the application involved.

All three problems can be solved efficiently by the Extended Euclidean Algorithm. Recall that, for $a(x), b(x) \in {\mathbb F}[x]$, not both zero, $\gcd(a(x),b(x))$ is defined to be the common divisor of a(x) and b(x)that has the greatest degree and is monic. We make the convention that $\gcd(0,0)=0$.

Facts:

1.

$\gcd(a(x),0) = a(x)$ (the result should be made monic).

2.

If a(x) = q(x)b(x) + r(x), then $\gcd(a(x),b(x)) = \gcd(b(x),r(x))$.

The second fact above is the so-called long division and the remainder r(x)is either zero or has a degree smaller than that of b(x). The Euclidean algorithm is simply a sequence of long divisions (repeated until the remainder becomes zero). The following extended Euclidean algorithm (EEA) also expresses each remainder as a linear combination of the original polynomials. To fix notation, let a(x) = r_-1 and b(x) = r₀, and we assume that $\deg a(x) \geq \deg b(x)$.

Extended Euclidean Algorithm

$$\begin{array}{lclclcl} & & & \hspace{.5cm} & r_{-1} & = & 1\... ...1}r_{t} + 0 & & 0 &=& u_{t+1}a(x) + v_{t+1}b(x) \\ \end{array}$$

where $\deg r_0 > \deg r_1 > \ldots > \deg r_t \geq 0$. Note that

$$\begin{eqnarray*}r_{i+1} & = & r_{i-1} - q_{i+1}r_{i} = (u_{i-1}a(x)+v_{i-1}b(x)... ...& = & (u_{i-1} - q_{i+1}u_i) a(x) + (v_{i-1} - q_{i+1}v_i) b(x). \end{eqnarray*}$$

We have

$$\begin{array}{llll} u_{-1} = 1, & u_0=0, & u_{i+1} = u_{i-1} ... ...1} = v_{i-1} - q_{i+1}v_i, & 0 \leq i \leq t. \\ \end {array}$$

The next theorem follows immediately from the algorithm.

Theorem 4.1   $\gcd(a(x),b(x)) =r_t= u_t a(x) + v_t b(x).$

The polynomials u_i and v_i have very nice properties.

Theorem 4.2   For $0\leq i\leq t+1$

u_i-1v_i - u_iv_i-1 = (-1)ⁱ,

so $\gcd(u_i,v_i)=1$. Furthermore,

$$a(x) = (-1)^i (v_i r_{i-1} - v_{i-1} r_i), \ \ b(x) = (-1)^i (-u_i r_{i-1} + u_{i-1} r_i), \ \ 0\leq i\leq t+1,$$

particularly,

$$a(x) = (-1)^{t+1} v_{t+1} r_t, \ \ b(x) = - (-1)^{t+1} u_{t+1} r_t.$$

Proof. Note that for $1\leq i\leq t+1$

$$\begin{bmatrix}u_{i-1} & v_{i-1} \\ u_i & v_i \end{bmatrix}\ ... ...in{bmatrix}u_{i-2} & v_{i-2} \\ u_{i-1} & v_{i-1} \end{bmatrix}$$

Iterate the above matrix equation i times yields

$$\begin{bmatrix}u_{i-1} & v_{i-1} \\ u_i & v_i \end{bmatrix}\ ... ...rix} \begin{bmatrix}u_{-1} & v_{-1} \\ u_0 & v_0 \end{bmatrix}$$

But

$$\begin{bmatrix}u_{-1} & v_{-1} \\ u_{0} & v_{0} \end{bmatrix}\ = \ \begin{bmatrix}1 & 0 \\ 0 & 1 \end{bmatrix}.$$

Since this is merely the identity matrix, it does not contribute anything to the above iteration process. Hence

$$u_{i-1}v_i - u_iv_{i-1} = det \begin{bmatrix}u_{i-1} & v_{i-... ...et \begin{bmatrix}0 & 1 \\ 1 & -q_j \end{bmatrix}\ = \ (-1)^i.$$

This proves the first statement. Note that

$$\begin{bmatrix}r_{i-1}\\ r_i \end{bmatrix}= \begin{bmatrix}u_... ...egin{bmatrix}v_{i} & -v_{i-1} \\ -u_i & u_{i-1} \end{bmatrix},$$

the second statement follows. $\Box$

Now we want to look at the relationship of the degrees of q_i and r_i. since $\deg r_{i+1} < \deg r_i$ for $0\leq{i}\leq{t}$, it follows from r_i-1= q_i+1 r_i + r_i+1 that

$$\deg r_{i-1} = \deg(q_{i+1}r_i) = \deg(q_{i+1}) + \deg(r_i),$$

or equivalently,

$$\deg r_i = \deg r_{i-1} - \deg q_{i+1}.$$

Hence, for $0\leq{i}\leq{t}$,

$$\deg r_i = \deg r_{-1} - (\deg q_1 + \deg q_2 + \dots + \deg q_{i+1}).$$ (6)

Note that $\deg r_{-1} = \deg a(x)$. We can now particularly express

$$\deg \gcd(a(x),b(x)) =\deg r_t= \deg a(x) - (\deg q_1 + \deg q_2 + \dots + \deg q_{t+1}).$$ (7)

Theorem 4.3   The Extended Euclidean Algorithm uses at most ${\mathcal O}(n^2)$ operations in ${\mathbb F}$ for $a(x),\:b(x) \in {\mathbb F}[x]$ with degrees $\leq{n}.$

Proof. We use the classical methods for polynomial multiplcation and division. For two polynomials a(x) and b(x) in ${\mathbb F}[x]$, the product a(x)b(x) can be computed in ${\mathcal O}(\deg a(x) \cdot \deg b(x))$operations in ${\mathbb F}$. And for long division, one can find $q(x),\:r(x) \in {\mathbb F}[x]$ such that

a(x) = q(x)b(x) + r(x),

where r(x) = 0, or $\deg\:r(x) < \deg\:b(x)$ in ${\mathcal O}((\deg q(x)\cdot (\deg r(x)))$ operations in ${\mathbb F}$.

So the Extended Euclidean Algorithm (EEA) uses at most the following number of operations:

$$\begin{eqnarray*}& & \sum_{i=1}^{t+1} {\mathcal O}(\deg q_i\cdot \deg r_{i-1}) \... ...cal O}(\deg a(x) \cdot \deg b(x)) \\ &=& {\mathcal O}(n^2), \\ \end{eqnarray*}$$

where we have used the facts that $\deg r_0 < \deg r_i$ and that of (7). $\Box$

Remark. EEA is fine to use for finite fields, since the coefficients of the intermediate polynomials never grow big. But for other fields (such as ${\mathbb Q}$), the sizes of the coefficients will grow exponentially.