Regular estimates for the complexity of polynomial multiplication and truncated Fourier transform

I. S. Sergeev

Prikladnaâ diskretnaâ matematika, no. 4 (2011), pp. 72-88

Résumé

In the present paper, some polynomial multiplication circuits being efficient either in complexity and depth or in complexity and memory size are proposed. Consequently, for instance, the multiplication of polynomials of the sum degree $n-1$, where $n=2^{n_1}+\dots+2^{n_s}$, $n_1>\dots>n_s$, over a ring with invertible 2 can be implemented via $M(n_1)+\dots+M(n_s)+\mathrm O(n)$ arithmetic operations over the ring with the depth $\max_i\{D(n_i)\}+\mathrm O(\log n)$, where $M(k)$ and $D(k)$ are respectively the complexity and the depth of the modulo $x^{2^k}+1$ multiplication circuit. As another example, the truncated DFT of order $n$ (i.e. the DFT of order $2^{\lceil\log_2n\rceil}$ reduced to the vectors of dimension $n$) can be implemented by a circuit of complexity $1,5n\log_2n+\mathrm O(n)$ and memory size $n+1$.

Détail

Keywords: arithmetic circuits, complexity, depth, memory size
Mots-clés : multiplication, Discrete Fourier Transform.