La sustitución de Kronecker es una técnica que lleva el nombre de Leopold Kronecker para determinar los coeficientes de un polinomio desconocido evaluándolo en un solo valor. Si p ( x ) es un polinomio con coeficientes enteros, y se elige que x sea una potencia de dos y mayor en magnitud que cualquiera de los coeficientes de p , entonces los coeficientes de cada término de se pueden leer directamente del binario. representación de p ( x ).
Una aplicación de este método es reducir el problema computacional de multiplicar polinomios al problema (potencialmente más simple) de multiplicar números enteros. Si p ( x ) y q ( x ) son polinomios con coeficientes conocidos, entonces se pueden usar estos coeficientes para determinar un valor de x que sea una potencia de dos lo suficientemente grande para que los coeficientes del producto pq ( x ) puedan leerse a partir de la representación binaria del número p ( x ) q ( x ). Dado que p ( x ) y q ( x ) son fáciles de determinar a partir de los coeficientes de p y q , este resultado muestra que la multiplicación polinomial se puede realizar en el momento de una única multiplicación binaria. [1]