Вычисления по модулю неприводимого полинома

[akor168]

Вопрос - какой наиболее эффективный метод вычисления остатка от деления одного полинома на другой в Q[x](Q - поле рациональных чисел), то есть нахождение r(x) по известным A(x) и P(x

Comments

[lucky__man]

А есть основания полагать, что можно сделать что-то существенно лучше, чем деление столбиком? Извините, если глупый вопрос, совсем не моя тема.

[akor168]

Вот это основной вопрос - есть ли что-то лучше деления столбиком.

[lucky__man]

Наверное, можно просто спросить - какой есть лучший способ деления больших чисел друг на друга? Мне кажется, что кроме мелких ускорений здесь и там, потенциально ничего лучшего пока не изобрели. (Потому что эта проблема стоит очень остро в VLSI и прочих embedded software, и все равно за десятилетия скорость деления аналогична скорости делению столбиком. Плюс-минус. Немного они научились ее сокращать, но это ассимптотически какие-то мелочи).
Единственное, что приходит в голову, это сделать эффективный делитель на K разрядов (где K - небольшое число, конечно), и затем применять деление в столбик не по одному разряду, а сразу по K разрядов. Ну и подобрать K по возможности оптимально.
А вот делитель на K разрядов уже оптимизировать как только можно, используя низкоуровневые трюки - большие таблицы для сокращения вычислений и т.п. Но больше мне как-то ничего в голову не приходит.
Буду рад ошибиться, но тогда почему не используют те же методы просто для деления длинных чисел в CPU?

[akor168]

В принципе если так рассуждать то надо произвести N=deg(P) делений c остатком(если мы выберем N точек и посчитаем значения). Собственно, можно ли сделать эти N делений совместно более эффективно...

[huzhepidarasa]

А не растут ли совершенно случайно коэффициенты результата экспоненциально со степенью А? Готовьтесь к результатам размером в гигабит.

[akor168]

Ага, потому и есть идея представлять к-ты через остаточные классы.

[huzhepidarasa]

При помощи китайской теоремы об остатках? Так это не поможет, битиков в таком представлении не меньше, чем в обычном. Или я чего-то не понимаю?

[akor168]

Не меньше, но работать то с этим по идее поприятнее должно быть. То есть сложение и умножение, конечно.

[math_mommy]

Если читаете по-ангийски, то можно глянуть, как это сделано в Магме:
http://magma.maths.usyd.edu.au/magma/
Они там современные методы внедряют. Ну, с некоторым отставанием, конечно, но для начала очень хорошо посмотреть.

[akor168]

А вот где там обсуждение алгоритмов?

[math_mommy]

У них есть документация, на тысячи страниц. В нашем универе (в Штатах) MAGMA была купленная, и все лежало прямо на сервере. Если у Вас нет, то посмотрите на сайте Documentaion --> Handbook --> Commutative Algebra, где-то там должно быть.