Let *R* be a ring. The univariate polynomial ring *R*[*x*]
can be implemented using different data types.

**Expression trees.**- All arithmetic operations are in
(1).
But the representation is
**not canonical**: two different expression trees can encode the same polynomial. Therefore operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in (*n*) where*n*is the degree of the polynomial. Even worst the equality-test is (*n*^{2}) (for non-balanced trees). **Arrays of coefficients.**- The polynomial
*p*(*x*) =*a*_{n}*x*^{n}+^{ ... }+*a*_{1}*x*+*a*_{0}(33)

is coded by a record consisting of- a single integer
*s*, - a single integer
*d**s*+ 1, - an array of size
*s*such that*a*_{0}+ ... +*a*_{n}*x*^{n}is represented by [*a*_{0},...,*a*_{n},...] and*d*=*n*.

*dense*becasue all*a*_{i}are coded, even those which are null. This representation is canonical. Hence operations like DEGREE, LEADING COEFFICIENT, REDUCTUM are in (1). Addition and equality-test are in (*n*) and multiplication is in (*n*^{2}). This representation is especially good when the ring of coefficients is a small prime field, i.e. /*p*with*p*prime and in the range [2, 2^{N}- 1]. - a single integer
**List of terms.**- The polynomial
*p*(*x*) =*a*_{n}*x*^{n}+^{ ... }+*a*_{1}*x*+*a*_{0}(34)

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

2004-04-27