Entrenador de división de polinomios

Cuando el divisor es x − r, todo el esquema de la división larga se reduce a una única fila de aritmética sobre los coeficientes: baja uno, multiplica por r, suma, repite. Esa es la división sintética, y es el mismo procedimiento que el método de Horner para evaluar un polinomio — razón por la cual el último número que escribes es a la vez el resto y el valor del polinomio en r. La eficiencia es real, no cosmética: un polinomio de grado 10 requiere así 10 multiplicaciones frente a 19 si calculas cada potencia por separado. Es como las bibliotecas numéricas evalúan realmente los polinomios, porque menos operaciones también significa menos error de redondeo acumulado.

La división de polinomios funciona igual que la división larga de números enteros que ya conoces: quitar un término cada vez y restar. Lo interesante aparece al dividir por un factor simple como (x - c): el resto que queda es exactamente p(c), el polinomio evaluado en c. Así, un resto de cero significa que c es una raíz, y lo descubres sin sustituir el número.

Cada suma de verificación CRC —el control de errores de un archivo guardado, un ZIP o un paquete de Ethernet— es una división de polinomios disfrazada. Los bits de datos se convierten en coeficientes de un polinomio enorme sobre el cuerpo GF(2), donde se calcula módulo 2 y la suma es solo un XOR. Ese polinomio se divide por un polinomio generador fijo, y el resto es la suma de verificación. El mismo algoritmo que este entrenador recorre a mano corre miles de millones de veces por segundo en el hardware de red.