Подстановка Кронекера - Kronecker substitution

Подстановка Кронекера это техника, названная в честь Леопольд Кронекер для определения коэффициентов неизвестного многочлен оценивая его по единственному значению. Если п(Икс) - многочлен с целыми коэффициентами, а Икс выбрана как сила двух и больше по величине, чем любой из коэффициентов п, то коэффициенты каждого члена могут быть прочитаны непосредственно из двоичное представление из п(Икс).

Одно из применений этого метода - уменьшать вычислительную задачу умножения многочленов на (потенциально более простую) задачу умножения целых чисел. п(Икс) и q(Икс) являются полиномами с известными коэффициентами, то можно использовать эти коэффициенты для определения значения Икс это достаточно большая степень двойки для того, чтобы коэффициенты произведения pq(Икс) для считывания из двоичного представления числа п(Икс)q(Икс). С п(Икс) и q(Икс) сами по себе легко определяются из коэффициентов при п и q, этот результат показывает, что полиномиальное умножение может быть выполнено за время одного двоичного умножения.[1]

Смотрите также

Рекомендации

  1. ^ фон цур Гатен, Иоахим; Герхард, Юрген (1999), Современная компьютерная алгебра, Cambridge University Press, стр. 243–244, ISBN  978-0-521-64176-0.