Глухо что-то. Теперь я знаю, что теорема Штрассена (доказательство пока не смотрел и не знаю, насколько оно конструктивно)
Там все просто. Сначала мы берем и с помощью свойства
переворачиваем все коэффициенты в равенстве
и получаем равенство
, а потом вычисляем
методом Ньютона и умножаем на
. См. напр. von zur Gathen, Modern computer algebra, §9.1.
с умножением можно легко разобраться хотя бы применяя быстрое дискретное преобразование Фурье.
В рациональных числах нет корней из единицы, поэтому
не получится. Можно обобщить умножение Шенхаге-Штрассена для умножения многочленов над произвольным кольцом, получится
, но не знаю, насколько это применимо на практике. см Modern computer algebra, §8.3
-- Пт май 31, 2013 01:09:03 --соответствующую литературу
von zur Gathen. Modern Computer Algebra
Brent, Zimmermann. Modern Computer Arithmetic
Bernstein. Fast multiplication and its applications
Burgisser, Clausen, Shokrollahi. Algebraic Complexity Theory
Arndt. Matters Computational