алгоритмы быстрого деления многочленов

[jorik]

Здравствуйте. Подскажите, пожалуйста, литературу по такому вопросу, как быстрое деление многочленов. Какие принципы используются в такого рода алгоритмах, если в самых общих чертах, можно ли разделить два многочлена с рациональными коэффициентами за $O(n\cdot \log(n))$ операций?

[jorik]

Глухо что-то. Теперь я знаю, что теорема Штрассена (доказательство пока не смотрел и не знаю, насколько оно конструктивно) дает положительный ответ на последний вопрос, точнее говоря, она утверждает, что сложность деления по порядку не выше, чем сложность умножения, а с умножением можно легко разобраться хотя бы применяя быстрое дискретное преобразование Фурье. Тем не менее основной вопрос об алгоритмах быстрого деления остается.

[jorik]

Нашел хорошую книжку: Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. - М.: МЦНМО, 2003.
С принципиальной точки зрения, вопрос снят.

Но, может быть, кто-то укажет какие-то другие быстрые алгоритмы по рассматриваемому вопросу и соответствующую литературу. Это тоже было бы интересно посмотреть.

[Xaositect]

jorik в сообщении #730609 писал(а):

Глухо что-то. Теперь я знаю, что теорема Штрассена (доказательство пока не смотрел и не знаю, насколько оно конструктивно)

Там все просто. Сначала мы берем и с помощью свойства $a(x) = \sum\limits_{i = 0}^n{a_i x^i} \Rightarrow \hat{a}(x) = x^n a(\frac{1}{x}) = \sum\limits_{i = 0}^n a_{n - i}x^i$ переворачиваем все коэффициенты в равенстве $a(x) = b(x)q(x) + r(x)$ и получаем равенство $\hat{a}(x) \equiv \hat{b}(x) \hat{q}(x) (\operatorname{mod} x^{n - m + 1})$, а потом вычисляем $b^{-1} \operatorname{mod} x^{n - m + 1}$ методом Ньютона и умножаем на $a$. См. напр. von zur Gathen, Modern computer algebra, §9.1.

jorik в сообщении #730609 писал(а):

с умножением можно легко разобраться хотя бы применяя быстрое дискретное преобразование Фурье.

В рациональных числах нет корней из единицы, поэтому $n\log n$ не получится. Можно обобщить умножение Шенхаге-Штрассена для умножения многочленов над произвольным кольцом, получится $n\log n \log \log n$, но не знаю, насколько это применимо на практике. см Modern computer algebra, §8.3

-- Пт май 31, 2013 01:09:03 --

jorik в сообщении #730650 писал(а):

соответствующую литературу

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

[jorik]

Xaositect в сообщении #730651 писал(а):

В рациональных числах нет корней из единицы, поэтому $n\log n$ не получится.

Да, действительно, но в данном случае деление в $\mathbb{R}$ тоже представляет интерес.

Цитата:

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

Спасибо, большое. Буду смотреть.