Замечания о быстром умножении многочленов, преобразовании Фурье и Хартли

Предложен быстрый алгоритм умножения действительных многочленов без использования комплексных чисел и быстрого преобразования Фурье. Эффективность этого алгоритма сравнивается с эффективностью алгоритма умножения, основанного на применении дискретного преобразования Хартли. Показано, что сложность преобразования Хартли совпадает с точностью до линейного слагаемого со сложностью преобразования Фурье, однако применение преобразования Хартли приводит к более эффективному алгоритму умножения. Приведены аналоги упомянутых результатов для конечных полей. Показано, что в некоторых случаях мультипликативные константы в оценках сложности умножения многочленов и преобразований Фурье и Хартли над конечными полями меньше, чем аналогичные константы в случае поля действительных чисел.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, и ФЦП “Интеграция”, проект 473.