Un preprocesado de coeficientes reduce a la mitad las multiplicaciones al evaluar polinomios
El autor sostiene que, preprocesando los coeficientes, un polinomio mónico se evalúa con ⌊n/2⌋+1 multiplicaciones en lugar de n. No hay paper, repositorio ni medidas de rendimiento.
Evaluar un polinomio de grado n con el método de Horner cuesta n multiplicaciones, n-1 si el polinomio es mónico. Una herramienta web publicada estos días asegura que, preprocesando antes los coeficientes, bastan ⌊n/2⌋+1 multiplicaciones para un polinomio mónico y una más para uno general. El ahorro no sale gratis: hay un paso previo sobre los coeficientes que se hace una sola vez, antes de empezar a evaluar.
La página es una calculadora. Se escribe el polinomio, se elige el cuerpo sobre el que se opera y devuelve los coeficientes ya preparados para ese cuerpo. El texto que la acompaña menciona tres terrenos donde ese recorte se nota: aproximar funciones como exp, sen o cos, y evaluar polinomios dentro de criptografía, hashing y teoría de códigos.
Dónde duele menos acortar
En esos campos la evaluación de polinomios no es un ejercicio de clase. Los esquemas de compromiso polinómico, los códigos de corrección de errores tipo Reed-Solomon y el hashing universal pasan por evaluar polinomios grandes, a veces con miles de coeficientes, dentro de bucles que se ejecutan millones de veces. Quitar la mitad de las multiplicaciones es ahí una mejora de constante, no de complejidad: el coste sigue creciendo de forma lineal con el grado.
Conviene mirar el otro lado de la balanza. El preprocesado se amortiza si el mismo polinomio se evalúa muchas veces, que es el escenario de una ronda criptográfica o de una rutina de decodificación. Si el polinomio se evalúa una sola vez, el trabajo extra puede comerse la ganancia, y el texto no detalla cuánto cuesta ese paso previo ni qué estructura tienen que tener los coeficientes para que funcione.
Lo que falta por ver
El anuncio es un párrafo y una calculadora. No hay artículo académico enlazado, ni repositorio, ni cifras medidas, ni comparación con las implementaciones que ya existen en bibliotecas criptográficas y de códigos. La afirmación, eso sí, es concreta y comprobable: cualquiera puede meter un polinomio en la herramienta y contar las multiplicaciones que salen.
Si el truco aguanta, el sitio donde hoy hay un bucle de Horner pasa a tener uno más corto, y ese tipo de rutinas está optimizado al detalle en las bibliotecas que sostienen firmas, pruebas de conocimiento cero y decodificación. La pregunta pendiente es si alguien lo lleva a una implementación real con números delante o si se queda en la calculadora.
