**Let
be a ring. The univariate polynomial ring
can be implemented using different data types.
**

**Expression trees.**- All arithmetic operations are in
.
But the representation is
**not canonical**: two different expression trees can encode the same polynomial. Therefore operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in where is the degree of the polynomial. Even worst the equality-test is (for non-balanced trees). **Arrays of coefficients.**- The polynomial
(34)

is coded by a record consisting of- a single integer ,
- a single integer ,
- an array of size such that is represented by and .

*dense*becasue all are coded, even those which are null. This representation is canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in . Addition and equality-test are in and multiplication is in . This representation is especially good when the ring of coefficients is a small prime field, i.e. with prime and in the range . **List of terms.**- The polynomial
(35)

is coded by the list of records where is a nonzero coefficient and such that is sorted decreasingly w.r.t. . This representation is said*sparse*, since only the nonzero are coded. This representation is also canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in . Moreover the operation REDUCTUM does not require coefficient duplication (on the contrary of the previous representation). Addition and equality-test are in and multiplication is in . This representation is especially good when the ring of coefficients is itself a ring of sparse polynomials.

*
*

2008-01-07