## Questions

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 .

Marc Moreno Maza
2008-03-18