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 x se elige para que sea una potencia de dos y una magnitud mayor que cualquiera de los coeficientes de p , entonces los coeficientes de cada término de pueden leerse 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 ) yq ( x ) son polinomios con coeficientes conocidos, entonces se pueden usar estos coeficientes para determinar un valor de x que sea una potencia de dos suficientemente grande para que los coeficientes del producto pq ( x ) puedan leerse de la representación binaria del número p ( x ) q ( x ). Dado que p ( x ) y q (x ) son en sí mismos sencillo determinar a partir de los coeficientes de p y q , este resultado muestra que la multiplicación polinómica se puede realizar en el momento de una sola multiplicación binaria. [1]
Ver también
Referencias
- ↑ von zur Gathen, Joachim ; Gerhard, Jürgen (1999), Álgebra informática moderna , Cambridge University Press, págs. 243–244, ISBN 978-0-521-64176-0.