Un algorithme de factorisation de polynômes sur corps finis qui utilise l'algèbre linéaire pour trouver la sous-algèbre de Berlekamp : on calcule une base de polynômes fixés par l'application de Frobenius (x ↦ x^q) modulo le polynôme et on extrait des facteurs non triviaux via des pgcd avec des combinaisons linéaires des éléments de la base.

Principe

Exploiter l'endomorphisme de Frobenius x ↦ x^q sur GF(q) : l'ensemble des classes de résidus fixées par Frobenius modulo un polynôme séparé forme un espace vectoriel ; résoudre les équations linéaires pour cet espace réduit la factorisation à de l'algèbre linéaire sur le corps de base suivie de séparations par pgcd.

Démonstration

Pour un f sans facteurs multiples dans GF(p)[x], calculer l'application q-linéaire induite par a ↦ a^p sur l'anneau quotient et construire la matrice de (Frobenius − Identité) ; son noyau fournit des polynômes dont les pgcd avec f effectuent des séparations non triviales, produisant des facteurs irréductibles après itérations.

Mauvaise application

Appliquer l'algorithme sans éliminer d'abord les facteurs répétés (factorisation sans facteurs multiples) est incorrect car les calculs de l'espace fixe de Frobenius supposent la séparabilité ; considérer Berlekamp comme pratique pour des q très grands sans améliorations modulaires ou aléatoires néglige la complexité et la mémoire requises.

Conséquence

Berlekamp fournit une méthode déterministe et exacte de factorisation sur corps finis, conceptuellement simple et efficace pour des tailles de corps modérées ; il a constitué la première approche pratique algébrique pour la factorisation et reste fondamental pour des étapes déterministes dans des algorithmes hybrides.

Inversion

Contrasté avec des méthodes de séparation aléatoires (par exemple Cantor–Zassenhaus) : au lieu d'utiliser l'algèbre linéaire pour trouver des invariants de façon déterministe, la réversion emploie l'aléa pour produire probabilistiquement des polynômes séparateurs rapides — ce sont deux cadres alternatifs pour le même objectif.

Limite

Conçu pour des polynômes sur corps finis et plus efficace sur des entrées sans facteurs multiples et de taille de corps modeste ; pour des corps très grands ou des polynômes de degré extrêmement élevé, des approches modulaires aléatoires sont souvent préférables en performances.

Tension sémantique

Tension entre l'approche déterministe et linéaire de Berlekamp et les algorithmes aléatoires : Berlekamp offre du déterminisme et une structure algébrique claire, tandis que les méthodes aléatoires sont souvent plus rapides en pratique pour de grands paramètres mais sans garantie déterministe.

Synthèse

L'algorithme de Berlekamp réduit la factorisation polynomiale sur corps finis à la résolution d'équations linéaires issues de l'action de Frobenius : en trouvant les classes de résidus fixées par Frobenius et en séparant par pgcd, il offre une voie algébrique déterministe pour l'extraction de facteurs.