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