- Explain why the elements of can be encoded as vectors with coordinates in . In the remaining questions, we will assume that this encoding is used.
- When does an element of have an inverse in ?
- With and , compute a quasi-inverse of and .
- Show that every , with , possesses a quasi-inverse.
- Show that a quasi-inverse of , with , can be computed in operations in .

**A quasi-inverse of
, with
,
tells us whether
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 non-zero polynomial
in
with degree less than
.
**

- Using GCD computations in , show that one can compute polynomials such that their product is and such that for each the polynomial is either zero or invertible modulo .

**Analyzing the complexity for computing
in question
is not easy and not required.
However, one special case is simpler: when
is squarefree,
that is, when for all non-constant polynomial
,
the polynomial
does not divide
.
From now on, we assume that
is squarefree.
**

- Using GCD computations in , show that one can compute polynomials such that , and is null modulo , and is invertible modulo . Show that and the inverse of modulo can be computed in operations in .

*
*

2008-03-18