Proof.
Clearly the polynomial
![$ f$](img166.png)
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
![$ f$](img166.png)
of degree
![$ n-1$](img192.png)
at one point costs
![$ 2 n - 2$](img196.png)
operations in
![$ {\bf k}$](img20.png)
.
So evaluating
![$ f$](img166.png)
at
![$ u_0, \ldots, u_{n-1}$](img205.png)
amounts to
![$ 2 n^2 - 2n$](img207.png)
.
Let us prove now that interpolating a polynomial at
![$ u_0, \ldots, u_{n-1}$](img205.png)
can be done in
![$ {\cal O}(n^2)$](img206.png)
operations in
![$ {\bf k}$](img20.png)
.
We first need to estimate the cost of computing the
![$ i$](img67.png)
-th interpolant
![$ L_i(u)$](img208.png)
.
Consider
![$ m_0 m_1$](img209.png)
,
![$ m_0 m_1 m_2$](img210.png)
, ...
![$ m = m_0 \cdots m_{n-1}$](img211.png)
where
![$ m_i$](img212.png)
is the monic polynomial
![$ m_i = x - u_i$](img213.png)
.
Let
![$ p_i = m_0 m_1 \cdots m_{i-1}$](img214.png)
and
![$ q_i = m / m_i$](img215.png)
for
![$ i = 1 \cdots n$](img216.png)
.
We have
![$\displaystyle L_i(u) \ = \ \frac{q_i}{q_i(u_i)}$](img217.png) |
(41) |
To estimate the cost of computing the
![$ L_i(u)$](img208.png)
's let us start with that of
![$ m$](img188.png)
.
Computing the product of the monic polynomial
![$ p_i = m_0 m_1 \cdots m_{i-1}$](img214.png)
of degree
![$ i$](img67.png)
by the monic polynomial
![$ m_i = x - u_i$](img213.png)
of degree
![$ 1$](img218.png)
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
![$ 2 \, i$](img222.png)
.
Hence computing
![$ p_2, \ldots, p_n = m$](img223.png)
amounts to
![\begin{displaymath}\begin{array}{rcl} {\Sigma}_{1 \leq i \leq n-1} \, 2 \, i & =...
...1} i \ \\ & = & 2 \, n \, (n-1)/2 \\ & = & n (n-1). \end{array}\end{displaymath}](img224.png) |
(42) |
Computing
![$ q_i$](img81.png)
implies a
division-with-remainder of the polynomial
![$ m$](img188.png)
of degree
![$ n$](img169.png)
by the polynomial
![$ m_i$](img212.png)
of degree
![$ 1$](img218.png)
.
This division will have
![$ n - 1 + 1$](img225.png)
steps, each step requiring
![$ 2$](img226.png)
operations
in
![$ {\bf k}$](img20.png)
.
Hence computing all
![$ q_i$](img81.png)
's amounts to
![$ n \, 2 \, n$](img227.png)
.
Since
![$ q_i$](img81.png)
has degree
![$ n-1$](img192.png)
computing each
![$ q_i(u_i)$](img228.png)
's
amounts to
![$ 2 n - 2$](img196.png)
operations in the base field
![$ {\bf k}$](img20.png)
(from Remark
4).
Then computing all
![$ q_i(u_i)$](img228.png)
's amounts to
![$ 2 n^2 - 2n$](img207.png)
.
Then computing each
![$ L_i(u) = q_i / q_i(u_i)$](img229.png)
from the
![$ q_i$](img81.png)
's and
![$ q_i(u_i)$](img228.png)
's costs
![$ n$](img169.png)
.
Therefore computing all
![$ L_i(u)$](img208.png)
's from scratch
amounts to
![$ n (n+1) + 2 \, n^2 + 2 n^2 - 2 n + n^2 = 6 n^2 - n$](img230.png)
.
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
![$ 2 \, n^2 - n$](img235.png)
.
Finally the total cost is
![$ 6 n^2 - 2n -1 + 2 \, n^2 - n = 8 \, n^2 - 2 \, n$](img236.png)
.