Proof.
Indeed, let
![$ g_1$](img61.png)
and
![$ g_2$](img62.png)
be solutions of
Equation (
8).
Then the product
![$ f (g_1 - g_2)$](img63.png)
is a multiple of
![$ x^{\ell}$](img64.png)
.
Since
![$ f(0) = 1$](img57.png)
then
![$ g_1(0) - g_2(0)$](img65.png)
must be
0
.
Hence there is a constant
![$ c \in R$](img66.png)
and polynomials
![$ h_1, h_2$](img67.png)
with degree less than
![$ {\ell} - 1$](img68.png)
such that
![$\displaystyle g_1(x) \ = \ h_1(x) \, x + c \ \ {\rm and} \ \ g_2(x) \ = \ h_2(x) \, x + c$](img69.png) |
(9) |
It follows that
![$ f (h_1 - h_2)$](img70.png)
is a multiple of
![$ x^{{\ell} -1}$](img71.png)
.
By repeating the same argument we show that
![$ h_1(0) = h_2(0)$](img72.png)
.
Then by induction on
![$ {\ell}$](img60.png)
we obtain
![$ g_1 = g_2$](img73.png)
.
Proof.
Theorem
1
tell us that Algorithm
2
computes the inverse of
![$ f$](img81.png)
modulo
![$ x^{2^r}$](img115.png)
.
Since
![$ x^{\ell}$](img64.png)
divides
![$ x^{2^r}$](img115.png)
, the result is also valid modulo
![$ x^{\ell}$](img64.png)
.
Before proving the complexity result, we point out
the following relation for
![$ i = 1 \cdots r$](img116.png)
.
![$\displaystyle g_i \ \equiv \ g_{i-1} \ \mod{ \ x^{2^{i-1}}}$](img117.png) |
(17) |
Indeed, by virtue of
Theorem
1
we have
![\begin{displaymath}\begin{array}{rcll} g_i & \equiv & 2 g_{i-1} - f \, {g_{i-1}}...
...}}} \\ & \equiv & g_{i-1} & \mod{ \ x^{2^{i-1}}} \\ \end{array}\end{displaymath}](img118.png) |
(18) |
Therefore when computing
![$ g_i$](img119.png)
we only care about powers of
![$ x$](img31.png)
in the range
![$ x^{2^{i-1}} \cdots x^{2^i}$](img120.png)
.
This says that
- half of the computation of
is made
during the last iteration of the for loop,
- a quater is made when computing
etc.
Now recall that
![$\displaystyle \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots \ = \ 1$](img123.png) |
(19) |
So
roughly the cost of the algorithm is in the order
of magnitude of the cost of the last iteration.
which consists of
- two multiplications of polynomials with degree less than
,
- a multiplication of a polynomial (with degree less than
)
by a constant,
- truncations modulo
- a subtraction of polynomials with degree less than
.
leading to
![$ 2 {\ensuremath{\mathsf{M}}}(2^r) + O(2^r)$](img125.png)
operations in
![$ R$](img1.png)
.
But this was not a formal proof, although the principle was correct.
Let us give a more formal proof.
The cost for the
-th iteration is
-
for the computation of
,
-
for the product
,
- and then the opposite of the upper half of
modulo
(which is the upper half
) takes
operations.
Thus we have
![$ \ensuremath{\mathsf{M}}(2^i) + \ensuremath{\mathsf{M}}(2^{i-1}) + 2^{i-1} \le \frac{3}{2} \, \ensuremath{\mathsf{M}}(2^i) + 2^{i-1}$](img133.png)
, resulting in a total running time:
![$\displaystyle \sum_{1\le{i}\le{r}}{\frac{3}{2} \, \ensuremath{\mathsf{M}}(2^i) ...
...\, \ensuremath{\mathsf{M}}(2^r)+2^r} = {3\,\ensuremath{\mathsf{M}}(\ell) +\ell}$](img134.png) |
(20) |
since
![$ 2\ensuremath{\mathsf{M}}(n) \le \ensuremath{\mathsf{M}}(2n)$](img135.png)
for all
Remark 6
Let us take a closer look at the computation of
![$\displaystyle g_{i-1} (2 - f \, g_{i-1}) \ \mod{ \ x^{2^{i}}}$](img142.png) |
(22) |
in Algorithm 2.
Consider first the product
. It satisfies:
![$\displaystyle f \, g_{i-1} \ \equiv \ 1 \ \mod{ \ x^{2^{i-1}}}$](img144.png) |
(23) |
Moreover, the polynomials
and
can be seen as polynomials
with degrees less than
and
respectively.
Hence, there exist polynomials
with degree less
than
such that we have:
![$\displaystyle f \, g_{i-1} = 1 + T x^{2^{i-1}} + S x^{2^{i}}.$](img147.png) |
(24) |
We are only interested in computing
.
In order to avoid computing
, let us observe that we have
![$\displaystyle f \, g_{i-1} \ \equiv \ (1 + S) + T x^{2^{i-1}} \mod{ \ x^{2^{i}} - 1}.$](img150.png) |
(25) |
In other words, the upper part (that is, the terms of
degree at least
) of the convolution product of
gives us exactly
.
So let us assume from now on that we have at hand
a primitive
-th root of unity, such that we can
compute DFT's.
Therefore, we can compute
at the cost of one
multiplication in degree less than
.
Consider now that we have computed
.
Viewing
and
as polynomials
with degrees less than
and
respectively,
there exist polynomials
with degree less
than
such that
![$\displaystyle g_{i-1} (2 - f \, g_{i-1}) = U + V x^{2^{i-1}} + W x^{2^{i}}$](img155.png) |
(26) |
We know that
.
Hence, we are only interested in computing
.
Similarly to the above, we observe that
![$\displaystyle g_{i-1} (2 - f \, g_{i-1}) \ \equiv \ (U + W) + V x^{2^{i-1}} \mod{ \ x^{2^{i}} - 1}$](img158.png) |
(27) |
Therefore, using DFT, we can compute
at the cost of one
multiplication in degree less than
.
It follows that, in the complexity analysis above
(in the proof of Theorem 2)
we can replace
by
leading to
instead of
.