Carrusel de Frobenius: bases normales sin búsqueda exhaustiva ✛ ✎
En cuanto se da energía, el carrusel de Frobenius se pone en marcha: cada elemento del cuerpo finito pasa a su descendiente q-ésimo, y las coordenadas se desplazan cíclicamente. Esta acción — el automorfismo de Frobenius — fue descrita por Gauss en sus investigaciones aritméticas, pero durante mucho tiempo solo se lograba poner en marcha el carrusel sin atascos a costa de búsquedas exhaustivas o manipulaciones matriciales.
El secreto de un giro suave está en la disposición correcta: hay que encontrar una base normal tal que el automorfismo simplemente permute cíclicamente sus elementos. Los autores del trabajo proponen no tantear billetes al azar, sino calcular de inmediato la lista de todos los lugares defectuosos. Para una extensión de grado n, construyen una familia de candidatos $β_t$ = (θ − t)⁻¹ — son como cabinas en una plataforma, y casi todas sirven.
El núcleo del método es el cálculo ultrarrápido del determinante de la matriz circulante con entradas polinomiales. La matriz se reduce a un polinomio característico en un álgebra con base de Gröbner, y un astuto levantamiento p-ádico evita los ceros en los denominadores de las fórmulas de Leverrier. Gracias a la técnica de conjuntos triangulares y composición modular, todo el cálculo toma un tiempo casi lineal respecto al tamaño de la entrada — O_ϵ((n² log q)^{1+ϵ}) operaciones de bits. Para cuerpos pequeños, se amplía temporalmente el cuerpo mediante multiplicación logarítmica, se construye allí un elemento normal y se desciende con cuidado de vuelta — y todo esto de forma determinista.
Ahora el carrusel se pone en marcha no con los ojos cerrados, sino con pleno conocimiento del punto de partida seguro. Esto otorga a los protocolos criptográficos una solidez garantizada, y a los sistemas de álgebra computacional, reproducibilidad de los cálculos. El siguiente paso es acelerar la proyección en base triangular hasta un tiempo verdaderamente lineal, con lo que la complejidad total se reduciría a Õ(n²). Hubo un tiempo en que Gauss hacía girar números a mano; hoy el carrusel algorítmico lo hace en milisegundos, dejándonos simplemente la admiración por las matemáticas puras.
Si n=1000 y q es un número primo ligeramente mayor que 10⁶, entonces los t «malos» no superan 10⁶, y solo habría que comprobar un millón de valores — una tarea factible incluso para una calculadora de escritorio. Todo el drama está en no hacer esa burda búsqueda por fuerza bruta, sino calcular un solo polinomio y evaluarlo en n(n−1)+1 puntos.