Замена Кронекера

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

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

См. также

• Продукт Кронекера