Euclidean Algorithm and its applications (continued)

MTHSC 985 Spring 2001 Clemson University
Topics on Computational Algebra Instructor: Shuhong Gao
Lecture 5, January 31 Scribe: Todd Mateer

Recall our conventions from the last lecture: ${\mathbb F}$ is any field and a(x) and $b(x) \in {\mathbb F}[x]$ which are nonzero. Assume that $\deg a(x) = m > \deg b(x) = n$. Also assume that $\deg 0 = - \infty$. Let r_-1 = a(x) and r₀ = b(x). The Extended Euclidean Algorithm computes

$$r_{i-1} = q_{i+1}\cdot r_{i} + r_{i+1}, \mbox{ for all $ 0 \leq i \leq t$,}$$

$$r_{i} = u_{i} \cdot a(x) + v_i \cdot b(x), \mbox{ for all $ -1 \leq i \leq t$}$$

where r_t+1 = 0, $r_i \neq 0$ for $i \leq i \leq t$,

$$\deg r_{-1} > \deg r_{0} > \deg r_{1} > .... > \deg r_{t},$$

and

  

$$u_{i+1} = u_{i-1} - q_{i-1} \cdot u_{i}, \ \ 1 \leq i \leq t,$$ u_-1 = 1, u₀ = 0, u₁ = 1, (8)

$$v_{i+1} = v_{i-1} - q_{i+1} \cdot v_{i}, \ \ 1 \leq i \leq t.$$ v_-1 = 0, v₀ = 1, v₁= -q₁, (9)

Then $gcd(a(x),b(x)) = r_{t} = u_{t} \cdot a(x) + v_{t} \cdot b(x)$.

Lemma 5.1   $\deg r_{i-1} + \deg v_{i} = m$ and $\deg r_{i-1} + \deg u_{i} = n$ for $1 \leq i \leq t.$

Proof. We have proved that $\deg r_{i-1} = m - (\deg q_{1} + .... + \deg q_{i})$for $1\leq i\leq t+1$. By (8), if $\deg u_{i} > \deg u_{i-1}$, then

$$\deg u_{i+1} = \deg (q_{i+1} \cdot u_{i}) = \deg q_{i+1} + \deg u_{i} > \deg u_{i},$$

as $\deg q_{i+1} \geq 1$. Since $\deg u_{i} > \deg u_{0}$, we have by induction that

$$\deg u_{i} = \deg q_{i}+\deg q_{i-1} + .... + \deg q_{2}, \ \ 2 \leq i \leq t.$$

Similarly,

$$\deg v_{i} = \deg q_{i} + \deg q_{i-1} + ... + \deg q_{1},\ \ 1 \leq i \leq t.$$

The lemma follows. $\Box$

Theorem 5.2   Let $a(x) \in {\mathbb F}[x]$ with degree $m \geq 1$. Then for any $b(x) \in {\mathbb F}[x]$ and any integers $j, k \geq 0$ with j + k = m - 1 there exist polynomials r(x) and v(x) in ${\mathbb F}[x]$ such that

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

and $\deg r(x) \leq j$, $\deg v(x) \leq k$; furthermore the ratio r(x) / v(x) is unique.

Proof. (Existence) We may assume that $\deg b(x) < m$. Apply the Extended Euclidean Algorithm to r_-1 = a(x) and r₀ = b(x). Stop the algorithm as soon as $\deg r_{i} \leq j$ (thus $\deg r_{i-1} \geq j+1$). Then $r_{i} = u_{i} \cdot a(x) + v_{i} \cdot b(x)$ and $v_i \ne 0$. We claim that $\deg v_{i} \leq k$ as $\deg v_{i} = m - \deg r_{i-1} \leq m - 1 - j = k$Hence we can take r(x) = r_i and v(x) = v_i.

(Uniqueness) Suppose we have another such pair $r_{1}(x), v_{1}(x) \in {\mathbb F}[x]$ with $v_1(x) \ne 0$. Then $r_{1}(x) \equiv b(x) v_{1}(x) \pmod{a(x)}$ and $r(x) \equiv b(x) v(x) \pmod{a(x)}$ imply that

$$r_{1}(x) v(x) - r(x) v_{1}(x) \equiv b(x) v_{1}(x) v(x) - b(x) v(x) v_{1}(x) \equiv 0 \pmod{a(x)},$$

i.e., $r_{1}(x) v(x) \equiv r(x) v_{1}(x) \pmod{a(x)}$. Note $\deg (r_{1}(x) v(x)) = \deg r_{1}(x) + \deg v(x) \leq j + k = m - 1$and $\deg (r(x) v_{1}(x)) \leq j + k = m - 1.$ Hence we have r₁(x) v(x) = r(x) v₁(x) i.e. r(x) / v(x) = r₁(x) / v₁(x). $\Box$.

Remark. For a given pair j,k with j+k=m-1, it is possible that the solution v(x) = v_icomputed by EEA may not be relatively prime to a(x), thus $r(x)/v(x) \bmod a(x)$ may not make sense (as $1/v(x) \bmod a(x)$ does not exist). In this case, there may not exist any $r(x), v(x) \in {\mathbb F}[x]$such that $\gcd(a(x),v(x))=1$ and

$$b(x) \equiv \frac{r(x)}{v(x)} \pmod{a(x)}, \ \ \deg r(x) \leq j, \deg v(x) \leq k.$$

For example, let a(x) = x^2s+1, and b(x) = x^s+1 -1. Then EEA computes

$$\begin{array}{rclll} a(x) = r_{-1} & = & x^{2s+1} & u_{-1} =1... ... r_3 & = & 0 & u_3 = 1 - x^{s+1} & v_3 = x^{2s+1}. \end{array}$$

For j=k=s, we have the solution r(x) = r₁ = x^s and v(x) = v₁ = -x^s, but the latter has a nontrivial gcd with a(x).

Exercise 5.3   Prove that it is impossible for any polynomials $r(x), v(x) \in {\mathbb F}[x]$ satisfying $v(0) \ne 0$ and

$$x^{s+1}-1 \equiv \frac{r(x)}{v(x)} \pmod{ x^{2s+1}}, \ \ \deg r(x) \leq s, \ \ \deg v(x) \leq s.$$

The above theorem holds also for any power series $b(x) = \sum_{i=0}^{\infty} b_i x^i$ where $b_i \in {\mathbb F}$and for a(x) = x^j+k+1. One can use EEA to compute all the solution pairs r(x), v(x) for $j, k=0,1,2, \ldots$. These solutions together are called the Padé approximation table for b(x).

Corollary 5.4   Let $t\geq 1$ be an integer. For any polynomial $S(x) \in {\mathbb F}[x]$, there exist polynomials $\omega(x)$ and $\sigma(x) \in {\mathbb F}[x]$such that

$$\sigma(x) \equiv \omega(x) S(x) \pmod{x^{2t+1}}$$

with $\deg \omega(x) \leq t$ and $\deg \sigma(x) \leq t$.

The above corollary solves a major step in decoding BCH codes where d = 2t+1 is the distance of the code, S(x) corresponds to the syndrome polynomial (known), $\omega(x)$ the error evaluator polynomial (unknown) and $\sigma(x)$ the error locator polynomial (unknown).

We mention another application of EEA.

Exercise 5.5   Given a sequence $s_0, s_1, \ldots, s_{2n} \in {\mathbb F}$, show how to find a nontrivial solution (if exists) to the following linear system

$$\left( \begin{array}{ccccc} s_{0} & s_{1} & s_{2} & \ldots & ... ...& s_{n+1} & s_{n+2} & \ldots & s_{2n} \end{array} \right) X=0$$

using ${\mathcal O}(n^2)$ operations in ${\mathbb F}$.

This problem is essentially the problem of finding the shortest linear recurrence relation for a given sequence $\{s_i\}_{i\geq 0}$. It can be solved via EEA in quadratic time. It can also be solved by the Berlekamp-Massey algorithm. We will show later these two algorithms are in fact equivalent.

Finally, we show how to solve Problems 4.1-4.3 efficiently. For Problem 4.1, EEA computes $d(x) = \gcd(a(x),b(x))$. Then a(x) and b(x) have a nontrivial common divisor iff $\deg d(x) \geq 1$. So this problem can be solved in quadratic time.

For Problem 4.2, for a solution to exist $\gcd(a(x),b(x))$ must divide r(x). To solve this problem, apply EEA to compute $d(x) = \gcd(a(x),b(x))$ and to find $u_1(x), v_1(x) \in {\mathbb F}[x]$ such that d(x)= u₁(x) a(x) + v₁(x) b(x). Then test if d(x) divide r(x). If not, no solutions exist. If yes, say r(x) = r₁(x) d(x) where $r_1(x) \in {\mathbb F}[x]$, then r(x) = u(x) a(x) + v(x) b(x) for u(x)=r₁(x) u₁(x) and v(x)= r₁(x) v₁(x). Hence Problem 4.2 can be solved in quadratic time.

For Problem 4.3, we make it more precise, namely: Given $a(x), b(x) \in {\mathbb F}[x]$ and integers j,k with $j+k = \deg a(x) -1$, find $r(x), v(x) \in {\mathbb F}[x]$ (if exist) such that $\gcd(v(x),a(x))=1$ and

$$b(x) \equiv \frac{r(x)}{v(x)} \pmod{a(x)}, \ \ \deg r(x) \leq j, \deg v(x) \leq k.$$

By Theorem 5.2 and its proof, this problem can also be solved in quadratic time. (The only remaining problem is to characterize exactly when solutions exist.)