Questions

$(1)$

Explain why the elements of ${\mathbb{L}}$ can be encoded as vectors with $n$ coordinates in ${\mathbb{K}}$ . In the remaining questions, we will assume that this encoding is used.

$(2)$

When does an element of ${\mathbb{L}}$ have an inverse in ${\mathbb{L}}$ ?

$(3)$

With ${\mbox{${\mathbb{K}}$}} = {\mbox{${\mathbb{Q}}$}}$ and $f = x^2 + 3x + 2$ , compute a quasi-inverse of $a_1 = x + 1$ and $a_2 = x - 1$ .

$(4)$

Show that every $a \in {\mbox{${\mathbb{L}}$}}$ , with $a \neq 0$ , possesses a quasi-inverse.

$(5)$

Show that a quasi-inverse of $a \in {\mbox{${\mathbb{L}}$}}$ , with $a \neq 0$ , can be computed in $O(n^2)$ operations in ${\mathbb{K}}$ .

A quasi-inverse of $a \in {\mbox{${\mathbb{L}}$}}$ , with $a \neq 0$ , tells us whether $a$ is invertible or a zero-divisor. In practice, the second case is inconvenient. For instance, division by a zero-divisor is not uniquely defined. This motivates the last questions of this exercise. From now on, we denote by $a$ a non-zero polynomial in ${\mbox{${\mathbb{K}}$}}[x]$ with degree less than $n$ .

$(6)$

Using GCD computations in ${\mbox{${\mathbb{K}}$}}[x]$ , show that one can compute polynomials $f_0, \ldots, f_e$ such that their product is $f$ and such that for each $i = 0 \cdots e$ the polynomial $a$ is either zero or invertible modulo $f_i$ .

Analyzing the complexity for computing $f_1, \ldots, f_e$ in question $(6)$ is not easy and not required. However, one special case is simpler: when $f$ is squarefree, that is, when for all non-constant polynomial $h \in {\mbox{${\mathbb{K}}$}}[x]$ , the polynomial $h^2$ does not divide $f$ . From now on, we assume that $f$ is squarefree.

$(7)$

Using GCD computations in ${\mbox{${\mathbb{K}}$}}[x]$ , show that one can compute polynomials $f_0, f_1 \in {\mbox{${\mathbb{K}}$}}[x]$ such that $f = f_0 f_1$ , and $a$ is null modulo $f_0$ , and $a$ is invertible modulo $f_1$ . Show that $f_0, f_1$ and the inverse of $a$ modulo $f_1$ can be computed in $O(n^2)$ operations in ${\mathbb{K}}$ .