Регулярные оценки сложности умножения многочленов и усеченного ДПФ

Строятся схемы для умножения многочленов и усеченного ДПФ (дискретного преобразования Фурье), эффективные с точки зрения сложности и глубины или сложности и объема памяти. Как следствие, умножение многочленов суммарной степени $n-1$, где $n=2^{n_1}+\dots+2^{n_s}$, $n_1>\dots>n_s$, над кольцом, в котором обратима двойка, можно выполнить со сложностью $M(n_1)+\dots+M(n_s)+\mathrm O(n)$ арифметических операций в этом кольце и глубиной $\max_i\{D(n_i)\}+\mathrm O(\log n)$, где $M(k)$ и $D(k)$ – соответственно сложность и глубина схемы умножения по модулю $x^{2^k}+1$. Усеченное ДПФ порядка $n$ (т.е. ДПФ порядка $2^{\lceil\log_2n\rceil}$, приведенное к векторам длины $n$) можно реализовать схемой сложности $1,5n\log_2 n+\mathrm O(n)$ и объема памяти $n+1$.