Найти остаток от большого фиксированного полинома, разделив его на небольшой неизвестный полином

9

Предположим, мы работаем в конечном поле. Нам дан большой фиксированный многочлен p (x) (скажем, степени 1000) над этим полем. Этот многочлен известен заранее, и нам разрешено выполнять вычисления с использованием большого количества ресурсов на «начальной стадии». Эти результаты могут быть сохранены в сравнительно небольших справочных таблицах.

В конце «начальной фазы» нам будет дан небольшой неизвестный многочлен q (x) (скажем, степени 5 или меньше).

Есть ли быстрый способ вычисления p (x) mod q (x), учитывая, что нам разрешено делать некоторые сложные вычисления в «начальной фазе»? Одним из очевидных способов является вычисление p (x) mod q (x) для всех возможных значений q (x). Есть лучший способ сделать это?

paulwaters
источник

Ответы:

3

Следующие алгоритмы хорошо работают, если базовое поле имеет очень маленький порядок .s

Предположим, мы знаем, что неприводимо с фиксированной степенью . Тогда, mod , мы знаем, что выполнено. Следовательно, достаточно предварительно вычислить .qdqxsd=xp(x)modxsdx

В общем случае может разлагаться на произведение неприводимых многочленов . В этом случае аналогичный аргумент применяется для вычисления по модулю каждого отдельно, а затем сложения результатов воедино. Поэтому нам действительно нужно вычислить для каждого .q(x)q=q1qrpq1,,qrp(x)modxsdxdd

Дэвид Харрис
источник
2

Я думаю, что есть довольно быстрый способ сделать это. Пусть коэффициенты пока неизвестного полинома быть , поэтому где есть некоторое малое число. Теперь давайте начнем вычислять где , где большой, а известны. Это мы делаем, уменьшая степень, используя равенства как . В конечном итоге мы получаем степень полинома, коэффициенты которого являются полиномами от (так какqbiq=i=0dbixidp(modq)p=i=0DaixiDaiaDxD=aDbdi=1d1bdixDi<d1biaiизвестны). Эти полиномы мы можем быстро вычислить, как только получим .q

domotorp
источник
-1

Смотрите отличные комментарии об этом посте ниже. :)


Предварительная обработка; вход: p(x)

  1. Коэффициент как .p(x)p(x)=i=01000(xiri)

  2. Сохраните это как таблицу различных корней и их соответствующих кратностей .Trjmj

Онлайн этап; вход: Q(Икс)

  1. Коэффициент как .Q(Икс)Q(Икс)знак равноΠязнак равно05(Икся-ря')

  2. Сохраните это как список различных корней и их соответствующих кратностей .LрJ'мJ'

  3. В то время как не пуст, удалить следующий корень / кратность из и любая точка , как в .LLT

  4. Считайте из модифицированной таблицы и выведите.п(Икс)модификацияQ(Икс)T


Другие комментарии:

  • Очевидно, вы хотите отсортировать таблицу и получить к ней доступ с помощью двоичного поиска (или дерева).T
  • (Пусть будет степенью .) Если вы хотите, чтобы выходные данные находились в представлении коэффициентов, вы можете просто сделать несколько FFT в конце, чтобы получить Время .dп(Икс)п(Икс)модификацияQ(Икс)О~(d)
  • В зависимости от того, как вы ее формализовали, вы, вероятно, можете предварительно вычислить множество различных способов, которыми вы заранее скомбинировали бы термины в (стиль динамического программирования), так что большинство (или все) умножений являются просто поиском. Тогда доминирующая стоимость - это количество поисков, или примерно . Если , это всего лишь несколько конкретных арифметических операций.TО(журналd)dзнак равно1000
Даниэль Апон
источник
2
В каком поле вы учитываете p? Насколько большой вы ожидаете, что это представление будет с точки зрения исходной области? А когда вы говорите, что считываете с модифицированной таблицы и выводите, что вы имеете в виду?
Дэвид Эппштейн
2
Это будет работать только в том случае, если вы работаете над полем, где и и разделены. Но это, кажется, зависит от ; в частности, вы не можете предварительно вычислить корни для . Кроме того, вычисление корней над таким большим полем займет время (как минимум); это не лучше, чем наивный алгоритм. пQQпQ|п|
Дэвид Харрис