Proof.
Clearly the polynomial
f of Relation (
31)
satisfies Relation (
30).
Hence the existence is clear.
The unicity follows from the fact that the difference of
two such polynomials has
 degree less than n and
 n roots
hence is the zero polynomial.
Proof.
We saw in Remark
7 that evaluating the polynomial
f
of degree
n at one point costs 2
n  2 operations in
.
So evaluating
f at
u_{0},...,
u_{n1} amounts to
2
n^{2}  2
n.
Let us prove now that interpolating a polynomial at
u_{0},...,
u_{n1} can be done in
(
n^{2}) operations in
.
We first need to estimate the cost of computing the
ith interpolant
L_{i}(
u).
Consider
m_{0}m_{1},
m_{0}m_{1}m_{2}, ...
m =
m_{0}^{ ... }m_{n1}
where
m_{i} is the monic polynomial
m_{i} =
x 
u_{i}.
Let
p_{i} =
m_{0}m_{1}^{ ... }m_{i1} and
q_{i} =
m/
m_{i} for
i = 1
^{ ... }n.
We have
L_{i}(u) = 
(32) 
To estimate the cost of computing the
L_{i}(
u)'s let us start with that of
m.
Computing the product of the monic polynomial
p_{i} =
m_{0}m_{1}^{ ... }m_{i1} of degree
i
by the monic polynomial
m_{i} =
x_{}u_{i} of degree 1 costs
 i multiplications (in the field ) to get
 u_{i} p_{i} plus
 i  1 additions (in the field ) to add
 u_{i} p_{i} (of degree i)
to x p_{i} (of degree i + 1 but without constant term)
leading to
2
i  1.
Hence computing
p_{2},...,
p_{n} =
m amounts to
2 i  1 
= 
2 i + 1 

= 
2i + n  1 

= 
2 n (n  1)/2 + n  1 

= 
(n  1)(n + 1) 

(33) 
Computing
q_{i} implies a
divisionwithremainder of the polynomial
m of degree
n by the polynomial
m_{i} of degree 1.
This division will have
n  1 + 1 steps, each step requiring 2 operations
in
.
Hence computing all
q_{i}'s amounts to
n 2
n.
Since
q_{i} has degree
n  1 computing each
q_{i}(
u_{i})'s
amounts to 2
n  2 operations in the base field
(from Remark
7).
Then computing all
q_{i}(
u_{i})'s amounts to
2
n^{2}  2
n.
Then computing each
L_{i}(
u) =
q_{i}/
q_{i}(
u_{i}) from the
q_{i}'s and
q_{i}(
u_{i})'s costs
n.
Therefore computing all
L_{i}(
u)'s from scratch
amounts to
(
n  1)(
n + 1) + 2
n^{2} + 2
n^{2}  2
n +
n^{2} = 6
n^{2}  2
n  1.
Computing f from the L_{i}(u)'s requires
 to multiply each L_{i}(u) (which is a polynomial of degree n  1) by the number v_{i}
leading to n^{2} operations in and
 to add these
v_{i} L_{i}(u) leading to n  1 additions
of polynomials of degree at most n  1
costing (n  1)n operations in
amounting to
2
n^{2} 
n.
Finally the total cost is
6
n^{2}  2
n  1 + 2
n^{2} 
n = 8
n^{2}  3
n  1