多項式に対する拡張ユークリッドアルゴリズム

ユークリッドの互除法による復号アルゴリズムの準備として。

多項式$${a(x)}$$を$${b(x)}$$でわった商を$${q(x)}$$, 余りを$${r(x)}$$とすると、

$$
a(x) = q(x)b(x) + r(x), deg\lbrace r(x)\rbrace < deg\lbrace b(x)\rbrace
$$

が成り立つ。$${a(x)}$$と$${b(x)}$$の最大公約数多項式は整数に対するユークリッドの互除法と同様に求められる。すなわち、$${a_0(x) = a(x), a_1(x) = b(x), a_2(x) = r(x), q_1(x) = q(x)}$$とおいて、

$$
a_0(x) = q_1(x)a_1(x) + a_2(x), deg\lbrace a_2(x) \rbrace < deg\lbrace a_1(x) \rbrace \\
a_1(x) = q_2(x)a_2(x) + a_3(x), deg\lbrace a_3(x) \rbrace < deg\lbrace a_2(x) \rbrace \\
\vdots \\
a_{n-2}(x) = q_{n-1}(x)a_{n-1}(x) + a_{n}(x), deg\lbrace a_{n}(x) \rbrace < deg\lbrace a_{n-1}(x) \rbrace \\
a_{n-1}(x) = q_n(x)a_n(x) \\
$$

となり、この操作は有限回で終了する。

このとき、$${a_n(x)}$$がモニックな多項式ならば、$${a_n(x)}$$が$${a(x)}$$と$${b(x)}$$の最大公約多項式$${GCD\lbrace a(x), b(x) \rbrace}$$となる。

行列で表現すると

$$
\begin{pmatrix}
a_0(x) \\
a_1(x) \\
\end{pmatrix}
=
\begin{pmatrix}
q_1(x) & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
a_1(x) \\
a_2(x) \\
\end{pmatrix}
$$

$$
\begin{pmatrix}
a_1(x) \\
a_2(x) \\
\end{pmatrix}
=
\begin{pmatrix}
q_2(x) & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
a_2(x) \\
a_3(x) \\
\end{pmatrix}
$$

$$
\vdots
$$

$$
\begin{pmatrix}
a_{n-2}(x) \\
a_{n-1}(x) \\
\end{pmatrix}
=
\begin{pmatrix}
q_{n-1}(x) & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
a_{n-1}(x) \\
a_n(x) \\
\end{pmatrix}
$$

$$
\begin{pmatrix}
a_{n-1}(x) \\
a_n(x) \\
\end{pmatrix}
=
\begin{pmatrix}
q_n(x) & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
a_n(x) \\
0 \\
\end{pmatrix}
$$

これにより、$${a_n(x)}$$と$${a_0(x)}$$と$${a_1(x)}$$で表す式

$$
\begin{pmatrix}
a_n(x) \\
0 \\
\end{pmatrix}
=
\begin{pmatrix}
q_n(x) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
q_{n-1}(x) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1} \\
\cdots 
\begin{pmatrix}
q_2(x) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
q_1(x) & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
a_0(x) \\
a_1(x) \\
\end{pmatrix} \\
= 
\begin{pmatrix}
0 & 1 \\
1 & -q_n(x) \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -q_{n-1}(x) \\
\end{pmatrix} \\
\cdots
\begin{pmatrix}
0 & 1 \\
1 & -q_2(x) \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -q_1(x) \\
\end{pmatrix}
\begin{pmatrix}
a_0(x) \\
a_1(x) \\
\end{pmatrix} \\
$$

が得られる。