La sustitución de Kronecker es una técnica que lleva el nombre de Leopold Kronecker y que sirve para determinar los coeficientes de un polinomio desconocido evaluándolo con un único 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 de la representación binaria 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 en sí mismos fáciles de determinar a partir de los coeficientes de p y q , este resultado muestra que la multiplicación de polinomios se puede realizar en el tiempo de una sola multiplicación binaria. [1]