Proof.
Clearly the polynomial
of Relation (
40)
satisfies Relation (
39).
Hence the existence is clear.
The unicity follows from the fact that the difference of
two such polynomials has
 degree less than
and

roots
hence is the zero polynomial.
Proof.
We saw in Remark
4 that evaluating the polynomial
of degree
at one point costs
operations in
.
So evaluating
at
amounts to
.
Let us prove now that interpolating a polynomial at
can be done in
operations in
.
We first need to estimate the cost of computing the
th interpolant
.
Consider
,
, ...
where
is the monic polynomial
.
Let
and
for
.
We have

(41) 
To estimate the cost of computing the
's let us start with that of
.
Computing the product of the monic polynomial
of degree
by the monic polynomial
of degree
costs

multiplications (in the field
) to get
plus

additions (in the field
) to add
(of degree
)
to
(of degree
but without constant term)
leading to
.
Hence computing
amounts to

(42) 
Computing
implies a
divisionwithremainder of the polynomial
of degree
by the polynomial
of degree
.
This division will have
steps, each step requiring
operations
in
.
Hence computing all
's amounts to
.
Since
has degree
computing each
's
amounts to
operations in the base field
(from Remark
4).
Then computing all
's amounts to
.
Then computing each
from the
's and
's costs
.
Therefore computing all
's from scratch
amounts to
.
Computing
from the
's requires
 to multiply each
(which is a polynomial of degree
) by the number
leading to
operations in
and
 to add these
leading to
additions
of polynomials of degree at most
costing
operations in
amounting to
.
Finally the total cost is
.