Let $k$ be a field equipped with finite encodings of its elements. Assume that there is an algorithm which decides whether an encoded element of $k$ is equal to $0$, and algorithms which compute the field operations $+$, $-$, $\cdot$, and division by a nonzero element, each in time polynomial in the total length of the input encodings. Assume moreover that these operation algorithms are polynomially size-bounded under polynomial-length straight-line field computations: there exists a polynomial $P \in \mathbb{R}[t]$ such that, for every integer $m \ge 1$, every finite tuple $(c_1,\dots,c_s)$ of encoded elements of $k$ with total encoding length $L$, and every straight-line computation of length at most $m$ starting from the given encodings and using the specified algorithms for $+$, $-$, $\cdot$, and division by previously computed nonzero elements, every encoded field element actually produced during the computation has encoding length at most $P(L+m)$.

A dense encoding of a polynomial $h \in k[x]$ is a finite coefficient list $(a_0,\dots,a_d)$ representing

\begin{align*} h=\sum_{i=0}^d a_i x^i. \end{align*}

The dense encoding is canonical if either $h=0$ and the list is $(0)$, or $d=\deg h$ and $a_d \ne 0$.

Then there are algorithms which, given canonical dense encodings of $f,g \in k[x]$, compute canonical dense encodings of $f+g$ and $fg$ in time polynomial in the total input length. If $g \ne 0$, there is also an algorithm which computes canonical dense encodings of the unique polynomials $q,r \in k[x]$ satisfying

\begin{align*} f=qg+r,\qquad r=0 \text{ or } \deg r<\deg g, \end{align*}

in time polynomial in the total input length.