Le manège de Frobenius : des bases normales sans essais ✛ ✎
Il suffit de mettre sous tension, et le manège de Frobenius se met en mouvement : chaque élément du corps fini passe à son q-ième successeur, et les coordonnées tournent en rond. Cette action — l'automorphisme de Frobenius — a été décrite par Gauss dans ses recherches arithmétiques, mais pendant longtemps, faire tourner le manège sans à-coups n'a été possible qu'au prix d'essais ou de manipulations matricielles.
Le secret d'une rotation fluide réside dans la disposition initiale : il faut trouver une base normale telle que l'automorphisme se contente de permuter ses éléments en cycle. Les auteurs de l'article proposent de ne pas tirer les tickets au hasard, mais de calculer directement la liste de toutes les places défectueuses. Pour une extension de degré n, ils construisent une famille de candidats $β_t$ = (θ − t)⁻¹ — c'est comme des nacelles sur le plateau, et presque toutes conviennent.
Le cœur de la méthode est le calcul ultra-rapide du déterminant d'une matrice circulante à entrées polynomiales. La matrice est réduite à son polynôme caractéristique dans une algèbre avec base de Gröbner, et une astucieuse remontée p-adique contourne les zéros dans les dénominateurs des formules de Leverrier. Grâce à la technique des ensembles triangulaires et à la composition modulaire, tout le calcul prend un temps presque linéaire en la taille de l'entrée — O_ϵ((n² log q)^{1+ϵ}) opérations binaires. Pour les petits corps, on étend temporairement le corps par une multiplication logarithmique, on y construit un élément normal, puis on redescend soigneusement — et tout cela est déterministe.
Le manège démarre désormais les yeux grands ouverts, avec une connaissance complète du point de départ sûr. Cela donne aux protocoles cryptographiques une robustesse garantie, et aux systèmes de calcul formel une reproductibilité des calculs. La prochaine étape est d'accélérer la projection dans la base triangulaire jusqu'à un temps vraiment linéaire, et alors la complexité totale tombera à O˜(n²). Autrefois, Gauss faisait tourner les nombres à la main ; aujourd'hui, le manège algorithmique le fait en quelques millisecondes, ne nous laissant que l'admiration des mathématiques pures.
Si n=1000 et q est un nombre premier un peu plus grand que 10⁶, alors il n'y a pas plus de 10⁶ « mauvais » t, et il ne faut essayer qu'un million de valeurs — une tâche à la portée d'une calculatrice de bureau. Tout le drame est de ne pas le faire par essais stupides, mais de calculer un seul polynôme et de l'évaluer en n(n−1)+1 points.