Let
be a commutative ring and let
be a power of
.
Let
be a primitive
-th root of unity.
We consider the following polynomial
in
.
Let
and
be two polynomials of degree less than
.
The goal of this exercise is to show that one can compute
asymptotically at the cost of multiplying
two polynomials in
with degree
.
Let
and
be the quotient and the remainder in the
division of
by
.
We define the polynomial
.
Marc Moreno Maza
2008-03-18