Chapitre 1

Rupture Méthodologique et
Décodage Polynomial Rapide

1.1 Équivalence entre la Formulation Matricielle

et Polynomiale (RHS)
Dans cette section, nous établissons le lien formel entre le système d’équa-
tions linéaires global résolu par la Forme Normale de Smith (SNF) dans les
travaux de Tchatchiem [?] et notre approche polynomiale à droite (Right-Hand
Side – RHS). Cette formulation permet de s’affranchir de la manipulation de
matrices de grande taille sur l’extension d’anneau S.
Soit R un anneau principal fini et S une extension libre de Galois de R de
rang m, munie de l’automorphisme de Frobenius σ. On note S[X; σ] l’anneau
des polynômes tordus (ou σ-polynômes) induit par la règle de commutation non
commutative :
X · a = σ(a)X, ∀a ∈ S (1.1)
Soit C un code de Gabidulin de longueur n et de dimension k défini sur S,
associé aux points d’évaluation linéairement indépendants g = (g1 , g2 , . . . , gn ) ∈
S n . Soit y = (y1 , y2 , . . . , yn ) = c + e le vecteur reçu, où c ∈ C et e désigne le
vecteur d’erreur de rang t ≤ b n−k 2 c.

Théorème 1.1 (Équivalence Algébrique RHS). La recherche du message ori-

ginal par la résolution du système linéaire global M · X = Y sur l’anneau S est
mathématiquement équivalente à la recherche d’un unique couple de σ-polynômes
(V (X), N (X)) ∈ S[X; σ]2 vérifiant l’équation clé polynomiale :

V (yi ) = N (gi ), ∀i ∈ {1, 2, . . . , n} (1.2)

sous les contraintes de degré degσ (V ) = t (V étant unitaire) et degσ (N ) ≤

k + t − 1.

1
 Pk−1 l
Démonstration. Soit F (X) = l=0 fl X ∈ S[X; σ] le polynôme de message
d’origine, tel que le mot de code émis s’écrit ci = F (gi ) pour tout i. Par définition
de la métrique de rang sur les anneaux principaux finis, l’espace d’erreur à droite
peut être représenté par lePnoyau d’un σ-polynôme localisateur d’erreur unique
t−1
et unitaire V (X) = X t + j=0 vj X j de degré t, tel que V (ei ) = 0 pour tout i.
En appliquant l’opérateur linéaire gauche V (X) à chaque composante du
vecteur reçu yi = F (gi ) + ei , et par linéarité de l’action des polynômes tordus,
nous obtenons :

V (yi ) = V (F (gi ) + ei ) = V (F (gi )) + V (ei ) (1.3)

Puisque V (ei ) = 0 par construction structurelle de l’espace d’erreur, l’équa-

tion se réduit de manière univoque à :

V (yi ) = V (F (gi )) (1.4)

Définissons le polynôme évaluateur d’erreur RHS par le produit tordu à

gauche :
N (X) = V (X) · F (X) (mod S[X; σ]) (1.5)
Par les propriétés d’additivité du degré dans l’anneau non commutatif S[X; σ],
nous avons :

degσ (N ) = degσ (V ) + degσ (F ) = t + (k − 1) = k + t − 1 (1.6)

L’évaluation polynomiale résultante donne immédiatement l’équation clé

RHS requise :
V (yi ) = N (gi ), ∀i ∈ {1, 2, . . . , n} (1.7)
Pour prouver l’équivalence stricte avec la formulation matricielle globale,
développons explicitementPcette équation en substituant
Pk+t−1 les formes denses des
t−1
polynômes V (X) = X t + j=0 vj X j et N (X) = l=0 nl X l :
 
t−1 k+t−1
yi[t] + [j] [l]
X X
v j yi  = nl gi (1.8)
j=0 l=0

où la notation exponentielle entre crochets désigne les puissances successives de

l’automorphisme de Frobenius généralisé, à savoir x[j] = σ j (x).
[t]
En isolant le terme invariant connu yi du côté droit (d’où l’appellation
Right-Hand Side), nous pouvons réordonner les termes sous la forme d’une com-
binaison linéaire d’inconnues :
k+t−1 t−1
[l] [j] [t]
X X
nl gi − vj yi = yi (1.9)
l=0 j=0

2
 Pour l’ensemble des n points d’évaluation collectés, ce système d’équations
se traduit directement sous la forme matricielle dense suivante :
 
n0
 .. 
 [k+t−1] [t−1]
  [t] 
g1 . . . g1 −y1 . . . −y1  .  y1
[k+t−1] [t−1]     [t] 
 g2 . . . g2 −y2 . . . −y2  nk+t−1  y2 

. .. .. ..  = .  (1.10)
.. ..

.   v0   .. 
.
. .
   
. . .
 . 
gn
[k+t−1]
. . . gn −y n
[t−1]
. . . −yn  ..  [t]
yn
vt−1

Ce système coïncide exactement avec l’équation matricielle globale M · X =

Y . Ainsi, résoudre ce système par la Forme Normale de Smith (SNF) équivaut de
manière isomorphe à identifier les coefficients du couple de σ-polynômes (V, N )
satisfaisant l’équation clé polynomiale.

1.2 Réduction algorithmique via l’L-EEA

L’intérêt fondamental de l’équivalence établie au théorème 1.1 réside dans le
fait que le couple de σ-polynômes (V, N ) peut être extrait de manière itérative
sans jamais instancier ni stocker la matrice globale M . Puisque l’équation clé
décrit une relation de congruence et de divisibilité algébrique à gauche dans
l’anneau non commutatif S[X; σ], le problème de décodage se ramène géométri-
quement à la recherche du plus grand commun diviseur à gauche (Left-GCD)
de deux polynômes d’interpolation initiaux.

1.2.1 Initialisation et Polynômes d’Interpolation

La première étape de la réduction polynomiale consiste à construire un poly-
nôme d’interpolation tordu initial, noté R0 (X) ∈ S[X; σ], qui capture l’ensemble
des points d’évaluation gi et des valeurs reçues yi . Par construction, ce polynôme
doit satisfaire la contrainte d’évaluation suivante :

R0 (gi ) = yi , ∀i ∈ {1, 2, . . . , n} (1.11)

Le calcul de R0 (X) s’effectue en un temps quadratique via l’algorithme d’in-

terpolation de Newton ou de Lagrange adapté aux polynômes tordus. Parallè-
lement, on définit le polynôme annulateur global, noté R−1 (X) ∈ S[X; σ], qui
admet tous les points d’information gi comme racines à droite :

R−1 (gi ) = 0, ∀i ∈ {1, 2, . . . , n} (1.12)

Ce polynôme R−1 (X) est unitaire et possède un degré degσ (R−1 ) = n. Il serves
de module de base pour l’espace des solutions, de sorte que toute relation valide
sur les points d’évaluation peut être réduite modulo R−1 (X).

3
1.2.2 Mécanisme Algorithmique et Invariants de Boucle
L’Algorithme d’Euclide Étendu Gauche (Left Extended Euclidean Algorithm
– L-EEA) est initialisé avec les deux suites polynomiales (Ri )i≥−1 et (Vi )i≥−1
définies par les conditions initiales suivantes :
( Qn
R−1 (X) = i=1 (X − gi ), V−1 (X) = 0
(1.13)
R0 (X) = Interpol(g, y), V0 (X) = 1

À chaque itération i ≥ 1, l’algorithme exécute une division euclidienne à

gauche du reste précédent Ri−2 (X) par le reste courant Ri−1 (X). Cette divi-
sion engendre un quotient gauche Qi (X) et un nouveau reste Ri (X) de degré
strictement inférieur :

Ri−2 (X) = Qi (X) · Ri−1 (X) + Ri (X), avec degσ (Ri ) < degσ (Ri−1 ) (1.14)

Simultanément, la suite des localisateurs d’erreurs auxiliaires Vi (X) est mise à

jour par la règle de transition standard de l’algorithme d’Euclide étendu :

Vi (X) = Vi−2 (X) − Qi (X) · Vi−1 (X) (1.15)

Par récurrence linéaire, les suites d’Euclide préservent l’invariant structurel

fondamental suivant pour chaque étape i :

Vi (X) · R0 (X) ≡ Ri (X) (mod R−1 (X)) (1.16)

Cette congruence implique qu’il existe un polynôme multiplicateur à gauche

Ui (X) ∈ S[X; σ] tel que :

Vi (X) · R0 (X) = Ui (X) · R−1 (X) + Ri (X) (1.17)

En évaluant cette identité polynomiale sur les points d’apprentissage gj , et

puisque R−1 (gj ) = 0 et R0 (gj ) = yj , l’invariant se projette directement sous la
forme :
Vi (yj ) = Ri (gj ), ∀j ∈ {1, 2, . . . , n} (1.18)
On constate que cette identité coïncide formellement avec l’équation clé RHS
du théorème 1.1. La condition d’arrêt de la boucle d’Euclide est dictée par la
borne de décodage unique. L’algorithme s’interrompt dès que le degré du reste
Ri (X) chute en dessous du seuil optimal :

n+k
degσ (Ri ) < (1.19)
2
À cet instant précis, le décodeur pose V (X) = Vi (X) comme polynôme locali-
sateur d’erreur RHS, et N (X) = Ri (X) comme polynôme évaluateur d’erreur
RHS.

4
1.2.3 Gestion des Diviseurs de Zéro et Pseudo-Division
Gauche
Pour formaliser ce mécanisme de réduction au sein de notre architecture
polynomiale, il convient de spécifier la structure locale de l’anneau de chaîne S.
Par définition, un tel anneau possède un idéal maximal unique, noté m, engendré
par un élément nilpotent π d’indice de nilpotence ν, de sorte que m = hπi et
π ν = 0. Tout élément non nul x ∈ S admet une représentation unique sous
la forme x = u · π v , où u ∈ S × désigne un élément inversible de l’anneau et
v ∈ {0, 1, . . . , ν − 1} définit la π-valuation de x, notée valπ (x) = v.
Dans l’anneau des polynômes tordus S[X; σ], cette filtration par les idéaux
induit une obstruction majeure lors de la phase d’annulation du monôme de
tête. Soit l’équation de réduction q · σ d (ri−1 ) = ri−2 introduite précédemment.
Deux configurations algébriques distinctes se présentent alors au décodeur :
1. Configuration régulière (valπ (ri−2 ) ≥ valπ (σ d (ri−1 ))) : L’élément ri−2
appartient à l’idéal à gauche engendré par σ d (ri−1 ). En posant ri−2 =
u1 π v1 et σ d (ri−1 ) = u2 π v2 (avec v1 ≥ v2 ), le coefficient du quotient gauche
se calcule directement par division des unités :

q = (u1 · u−1
2 )·π
v1 −v2
(1.20)

Dans ce cas, l’élimination standard s’applique sans altérer le dividende

Ri−2 (X).
2. Configuration singulière (valπ (ri−2 ) < valπ (σ d (ri−1 ))) : L’élément
ri−2 n’appartient pas à l’idéal engendré par le coefficient de tête du di-
viseur. Il est alors impossible de trouver un scalaire q ∈ S permettant
d’annuler le monôme de tête de Ri−2 (X). Pour surmonter cette singula-
rité sans rompre la convergence polynomiale, nous introduisons une opé-
ration de pseudo-division tordue gauche. On définit un facteur d’échelle
multiplicatif α ∈ m, déterminé par la différence positive des valuations :

α = π v2 −v1 (1.21)

Le dividende Ri−2 (X) est alors modifié à gauche par ce facteur d’échelle
avant l’étape de soustraction. L’invariant de l’L-EEA est préservé en ap-
pliquant le même facteur α au polynôme localisateur auxiliaire Vi−2 (X).
L’équation d’élimination tordue se reformule alors sous la forme :

α · Ri−2 (X) − q · X d · Ri−1 (X) = Ri (X) (1.22)

où le quotient ajusté q devient calculable puisque, par construction, valπ (α·

ri−2 ) = valπ (σ d (ri−1 )).
Afin d’assurer la reproductibilité de cette rupture algorithmique, l’ensemble
de cette procédure de gestion des diviseurs de zéro est formalisé dans l’algo-
rithme ??.

5
Algorithme 1.2.1 : Pseudo-division euclidienne à gauche dansPn S[X; σ]j
Entrées : Dividende A(X) = m j
P
j=0 a j X , Diviseur B(X) = j=0 bj X ∈ S[X; σ]
Sorties : Quotient gauche Q(X), Reste gauche R(X) tels que αA(X) = Q(X)B(X) + R(X)
1. Initialiser R(X) ← A(X), Q(X) ← 0, n ← degσ (B), bn ← lc(B)
2. Tant que degσ (R) ≥ n et R(X) 6= 0 faire
3. m ← degσ (R), rm ← lc(R), d ← m − n
4. bshift ← σ d (bn )
5. v1 ← valπ (rm ), v2 ← valπ (bshift )
6. Si v1 ≥ v2 alors % Configuration régulière
7. qcoeff ← (rm · b−1shift ) · π
v1 −v2

8. Sinon % Configuration singulière : application du facteur d’échelle

9. α ← π v2 −v1
10. R(X) ← α · R(X)
11. Q(X) ← α · Q(X)
12. qcoeff ← (lc(R) · b−1shift )
13. Fin Si
14. TQ (X) ← qcoeff X d
15. Q(X) ← Q(X) + TQ (X)
Psub (X) ← n d
P
j+d
16. j=0 qcoeff · σ (bj ) X % Multiplication tordue gauche
17. R(X) ← R(X) − Psub (X)
18. Fin Tant que
19. Retourner Q(X), R(X)

Cette sous-routine garantit la décroissance stricte du degré topologique de la

suite des restes, préservant ainsi la convergence quadratique de l’L-EEA. Bien
que l’introduction des facteurs d’échelle α modifie localement le degré algébrique
des idéaux, le théorème d’unicité de l’espace d’erreur assure que le polynôme
localisateur final V (X) extrait à la convergence reste libre et unitaire dans le
module d’extension.

1.2.4 Exemple Numérique de Pseudo-Division Gauche sur

Z/4Z
Afin d’illustrer le comportement de l’algorithme 1.2.1 face à une configu-
ration singulière induite par un diviseur de zéro, considérons l’anneau de base
R = Z/4Z. Son unique idéal maximal est m = h2i, impliquant que π = 2 et
son indice de nilpotence est ν = 2 (puisque 22 ≡ 0 (mod 4)). Les éléments non
inversibles de cet anneau sont {0, 2}.
Soit σ l’automorphisme trivial (identité) pour simplifier la lecture, de sorte
que l’anneau des polynômes tordus se ramène ici à l’anneau de polynômes com-
mutatif (Z/4Z)[X].
Soient les deux polynômes initiaux suivants :
(
A(X) = 3X 2 + 1X + 2 (Dividende, deg(A) = 2)
(1.23)
B(X) = 2X + 3 (Diviseur, deg(B) = 1)

Le coefficient de tête du diviseur est lc(B) = b1 = 2, qui est un diviseur de

zéro non inversible de valuation val2 (2) = 1. Nous initialisons le reste courant

6
R(X) = A(X) et le quotient Q(X) = 0.

Itération 1 : Élimination du terme en X 2

– Analyse des degrés et coefficients : m = deg(R) = 2, n = deg(B) = 1,
d’où le décalage d = m − n = 1. Le coefficient de tête du reste est r2 = 3
(valuation v1 = val2 (3) = 0). Le coefficient du diviseur décalé est bshift =
σ 1 (2) = 2 (valuation v2 = val2 (2) = 1).
– Détection de la configuration : Puisque v1 < v2 (0 < 1), nous sommes
en configuration singulière. Le coefficient 2 ne peut pas diviser 3 dans
Z/4Z.
– Application du facteur d’échelle : Nous calculons le facteur d’échelle
α = π v2 −v1 = 21−0 = 2. Nous mettons à jour le reste en le multipliant par
2:
R(X) ← 2 · (3X 2 + 1X + 2) = 6X 2 + 2X + 4 ≡ 2X 2 + 2X + 0 (mod 4)
(1.24)
Le quotient temporaire subit la même mise à jour : Q(X) ← 2 · 0 = 0.
– Calcul du monôme du quotient : Le nouveau coefficient de tête de
R(X) est lc(R) = 2 (valuation 1). L’équation devient qcoeff ·2 ≡ 2 (mod 4),
ce qui donne qcoeff = 1. Le terme du quotient est TQ (X) = 1X 1 = X.
– Mise à jour des polynômes :
Q(X) = 0 + X = X (1.25)
Psub (X) = X · (2X + 3) = 2X 2 + 3X (1.26)
2 2
R(X) = (2X + 2X) − (2X + 3X) = −1X ≡ 3X (mod 4) (1.27)
À la fin de cette itération, deg(R) = 1, la boucle continue car deg(R) ≥
deg(B).

Itération 2 : Élimination du terme en X

– Analyse des degrés et coefficients : m = deg(R) = 1, n = deg(B) = 1,
d’où d = 1 − 1 = 0. Nous avons r1 = 3 (v1 = 0) and bshift = 2 (v2 = 1).
– Application du facteur d’échelle : À nouveau, v1 < v2 , configuration
singulière. Le facteur d’échelle est α = 21−0 = 2.
– Mise à jour par α :
R(X) ← 2 · (3X) = 6X ≡ 2X (mod 4) (1.28)
Q(X) ← 2 · (X) = 2X (1.29)
– Calcul du monôme du quotient : L’équation lc(R) = qcoeff · bshift
devient 2 = qcoeff · 2, d’où qcoeff = 1. Le terme est TQ (X) = 1X 0 = 1.
– Mise à jour finale :
Q(X) = 2X + 1 (1.30)
Psub (X) = 1 · (2X + 3) = 2X + 3 (1.31)
R(X) = 2X − (2X + 3) = −3 ≡ 1 (mod 4) (1.32)

7
 L’algorithme s’arrête car deg(R) = 0 < deg(B). Le facteur d’échelle glo-
bal accumulé est αtotal = 2 · 2 = 4 ≡ 0 (mod 4) au sens de l’anneau, mais
structurellement l’identité de pseudo-division s’écrit bien :

(2 · 2) · A(X) = Q(X) · B(X) + R(X) (1.33)

Vérifions numériquement l’égalité polynomiale avant réduction totale par les

diviseurs de zéro pour valider l’invariant :

Q(X)B(X)+R(X) = (2X+1)(2X+3)+1 = 4X 2 +6X+2X+3+1 = 4X 2 +8X+4

(1.34)
En appliquant la réduction modulo 4, nous obtenons bien 0, ce qui correspond
strictement à la valeur de la multiplication de gauche accumulée 4 · A(X) ≡ 0
(mod 4).
Cet exemple valide la capacité de l’algorithme à forcer la réduction du de-
gré topologique (le reste final est de degré 0, c’est-à-dire une constante) même
lorsque l’algèbre linéaire classique s’effondrerait face à des coefficients non in-
versibles.

1.2.5 Exemple Numérique de Pseudo-Division Gauche sur

Z/12Z
Afin d’illustrer le comportement de l’algorithme 1.2.1 face à une configu-
ration singulière induite par un diviseur de zéro au sein d’un anneau princi-
pal fini non local, considérons l’anneau de base R = Z/12Z. Cet anneau pré-
sente des diviseurs de zéro non triviaux issus de sa décomposition structurelle
Z/12Z ∼ = Z/3Z × Z/4Z. L’élément π = 2 engendre l’idéal des éléments pairs, et
les éléments non inversibles de cet anneau sont {0, 2, 3, 4, 6, 8, 9, 10}.
Soit σ l’automorphisme trivial (identité) pour simplifier la lecture, de sorte
que l’anneau des polynômes tordus se ramène ici à l’anneau de polynômes com-
mutatif (Z/12Z)[X].
Soient les deux polynômes initiaux suivants :
(
A(X) = 1X 2 + 2X + 5 (Dividende, deg(A) = 2)
(1.35)
B(X) = 4X + 1 (Diviseur, deg(B) = 1)

Le coefficient de tête du diviseur est lc(B) = b1 = 4, qui est un diviseur de

zéro non inversible possédant une valuation val2 (4) = 2 (puisque 4 = 1 · 22 ).
Nous initialisons le reste courant R(X) = A(X) et le quotient Q(X) = 0.

Itération 1 : Élimination du terme en X 2

– Analyse des degrés et coefficients : m = deg(R) = 2, n = deg(B) = 1,
d’où le décalage d = m − n = 1. Le coefficient de tête du reste est r2 = 1
(valuation v1 = val2 (1) = 0, car 1 est inversible dans Z/12Z). Le coefficient
du diviseur décalé est bshift = σ 1 (4) = 4 (valuation v2 = val2 (4) = 2).

8
 – Détection de la configuration : Puisque v1 < v2 (0 < 2), nous sommes
en configuration singulière. Le coefficient 4 ne peut pas diviser 1 dans
Z/12Z.
– Application du facteur d’échelle : Nous calculons le facteur d’échelle
local requis pour aligner les valuations, soit α = π v2 −v1 = 22−0 = 4. Nous
mettons à jour le reste courant en le multipliant à gauche par 4 :

R(X) ← 4 · (1X 2 + 2X + 5) = 4X 2 + 8X + 20 ≡ 4X 2 + 8X + 8 (mod 12)

(1.36)
Le quotient temporaire subit la même mise à jour : Q(X) ← 4 · 0 = 0.
– Calcul du monôme du quotient : Le nouveau coefficient de tête de
R(X) est lc(R) = 4 (valuation 2). L’équation de tête devient qcoeff · 4 ≡ 4
(mod 12), ce qui donne trivialement qcoeff = 1. Le terme du quotient
correspondant est TQ (X) = 1X 1 = X.
– Mise à jour des polynômes :

Q(X) = 0 + X = X (1.37)

Psub (X) = X · (4X + 1) = 4X 2 + X (1.38)

2 2
R(X) = (4X + 8X + 8) − (4X + X) = 7X + 8 (mod 12) (1.39)
À la fin de cette première étape, deg(R) = 1. La boucle de contrôle se
poursuit puisque la condition deg(R) ≥ deg(B) est toujours satisfaite.

Itération 2 : Élimination du terme en X

– Analyse des degrés et coefficients : m = deg(R) = 1, n = deg(B) = 1,
d’où un décalage nul d = 1 − 1 = 0. Nous identifions le coefficient de tête
du reste r1 = 7 (v1 = val2 (7) = 0, car 7 est impair et donc inversible
premier avec 12) et le diviseur de tête stable bshift = 4 (v2 = 2).
– Application du facteur d’échelle : Constatant à nouveau que v1 < v2 ,
une nouvelle configuration singulière est levée. Le facteur d’échelle est
calculé par α = 22−0 = 4.
– Mise à jour par α :

R(X) ← 4 · (7X + 8) = 28X + 32 ≡ 4X + 8 (mod 12) (1.40)

Q(X) ← 4 · (X) = 4X (1.41)

– Calcul du monôme du quotient : L’équation d’annulation prend la
forme lc(R) = qcoeff · bshift , soit 4 ≡ qcoeff · 4 (mod 12), d’où qcoeff = 1. Le
terme résultant est TQ (X) = 1X 0 = 1.
– Mise à jour finale du système :

Q(X) = 4X + 1 (1.42)

Psub (X) = 1 · (4X + 1) = 4X + 1 (1.43)

R(X) = (4X + 8) − (4X + 1) = 7 (mod 12) (1.44)

9
 L’algorithme s’interrompt de manière déterministe puisque le degré topolo-
gique est strictement réduit : deg(R) = 0 < deg(B). Le facteur d’échelle cumulé
itérativement au cours des réductions successives s’élève à αtotal = 4·4 = 16 ≡ 4
(mod 12). L’identité de pseudo-division gauche se formalise ainsi :

αtotal · A(X) = Q(X) · B(X) + R(X) (1.45)

Pour valider l’intégrité algébrique de l’invariant développé dans nos preuves

de convergence, calculons explicitement le membre de droite :

Q(X)B(X)+R(X) = (4X+1)(4X+1)+7 = 16X 2 +4X+4X+1+7 = 16X 2 +8X+8

(1.46)
En appliquant la réduction modulo 12 sur l’anneau R, le polynôme se simplifie
sous la forme :

16X 2 + 8X + 8 ≡ 4X 2 + 8X + 8 (mod 12) (1.47)

Cette expression coïncide rigoureusement avec le membre de gauche où αtotal ·

A(X) = 4 · (1X 2 + 2X + 5) = 4X 2 + 8X + 20 ≡ 4X 2 + 8X + 8 (mod 12).
Cet exemple valide la robustesse de notre formalisme. Malgré la présence
de diviseurs de zéro non locaux et non nilpotents au sein de Z/12Z (qui pa-
ralyseraient un algorithme d’Euclide standard par des inversions impossibles),
l’introduction dynamique des facteurs d’échelle garantit une décroissance topo-
logique stricte vers un reste de degré nul.

1.3 Accélération par Parallélisation via la Décom-

position CRT
Bien que l’introduction de l’L-EEA abaisse la complexité théorique du dé-
codage à une forme quadratique O(n2 ), la manipulation directe de structures
algébriques sur des anneaux principaux finis non locaux complexes induit un
surcoût non négligeable lors de la gestion itérative des pseudo-divisions. Pour
optimiser l’architecture de calcul, nous exploitons ici une propriété structurelle
forte démontrée par Tchatchiem [?] : la décomposition de tout anneau principal
fini en un produit direct d’anneaux de chaîne finis (locaux).
Nous formalisons dans cette section une stratégie de décodage distribué s’ap-
puyant sur le Théorème des Restes Chinois (Chinese Remainder Theorem –
CRT). L’objectif est de fragmenter le problème global en ρ sous-problèmes in-
dépendants s’exécutant en parallèle sur des structures locales simplifiées, avant
de recombiner les messages par isomorphisme.

1.3.1 Isomorphisme de Structure de l’Anneau et des Ex-

tensions
Soit R l’anneau principal fini de base. Il existe un ensemble unique d’idéaux
maximaux {m1 , . . . , mρ } induisant la décomposition en produit direct d’anneaux

10
de chaîne locaux R(i) :
R∼
= R(1) × R(2) × · · · × R(ρ) (1.48)
Par extension canonique, cet isomorphisme se propage naturellement à l’exten-
sion de Galois libre S de dimension m, ainsi qu’à l’anneau des polynômes tordus
S[X; σ]. Nous pouvons ainsi écrire :
S[X; σ] ∼
= S(1) [X; σ1 ] × S(2) [X; σ2 ] × · · · × S(ρ) [X; σρ ] (1.49)
où chaque S(i) est une extension de Galois locale sur l’anneau de chaîne R(i) , et
σi désigne la restriction de l’automorphisme de Frobenius global au sous-anneau
local correspondant.
Un élément macroscopique x ∈ S est ainsi bijectivement représenté par
son vecteur de projections locales, noté x = (x(1) , x(2) , . . . , x(ρ) ), où x(i) ≡ x
ν(i)
(mod mi ).

1.3.2 Algorithme de Décodage Parallèle Distribué

L’existence de cet isomorphisme polynomial permet de déporter l’intégra-
lité de l’Algorithme d’Euclide Étendu Gauche (L-EEA) au sein des structures
locales. Le processus se déploie selon le triptyque algorithmique suivant :
1. Phase de Projection (Splitting) : Le vecteur reçu global y = (y1 , . . . , yn ) ∈
S n et les points d’évaluation globaux g = (g1 , . . . , gn ) ∈ S n sont pro-
jetés sur chacune des ρ composantes locales. Pour chaque sous-anneau
i ∈ {1, . . . , ρ}, on extrait :
y (i) = y1 (mod S(i) ), . . . , yn (mod S(i) ) ∈ S(i)
n


(1.50)

g (i) = g1 (mod S(i) ), . . . , gn (mod S(i) ) ∈ S(i)

n


(1.51)
2. Phase de Décodage Local Parallèle : Les ρ instances de décodage sont
exécutées de manière strictement isolée et simultanée (via une architecture
matérielle multi-threads ou FPGA dédiés). Sur chaque composante i, l’L-
EEA polynomial résout l’équation clé locale associée :
(i)
(i)

V (i) yj = N (i) gj , ∀j ∈ {1, . . . , n} (1.52)
Chaque sous-décodeur extrait indépendamment son propre polynôme d’in-
formation local F (i) (X) ∈ S(i) [X; σi ] de degré inférieur à k par division à
gauche.
3. Phase de Recombinaison Globale (CRT Lift) : Une fois les ρ poly-
nômes de message locaux
Pk−1 obtenus, les coefficients du polynôme d’informa-
tion global F (X) = l=0 fl X l sont reconstruits coefficient par coefficient.
Pour chaque degré l ∈ {0, . . . , k − 1}, le symbole global fl ∈ S est calculé
via la formule explicite d’Euler-Bézout du CRT :
ρ
(i)
X
fl = fl · Ei (mod S) (1.53)
i=1

11
 où les {E1 , . . . , Eρ } désignent les éléments orthogonaux idempotents de
2
P de base de l’isomorphisme vérifiant Ei = Ei , Ei Ej =
l’anneau (les vecteurs
0 pour i 6= j, et Ei = 1).

1.3.3 Gain de Performance et Analyse Métrologique

L’avantage de cette architecture distribuée face au formalisme de la thèse de
Tchatchiem est double :
– Simplification algébrique locale : Au sein de chaque instance locale
S(i) , l’idéal maximal est unique. La gestion des diviseurs de zéro dans la
sous-routine de pseudo-division gauche (Algorithme 1.1) se réduit à une
simple vérification de puissance de l’élément générateur πi , éliminant les
calculs de pgcd complexes requis sur un anneau global non local (comme
l’analyse des facteurs croisés rencontrée dans l’exemple sur Z/12Z).
– Accélération temporelle : Soit τ (n) le temps requis pour exécuter une
opération tordue dans l’anneau global S. Dans la structure locale S(i) , le
cardinal est plus petit, et le coût d’une opération tombe à τi (n) ≈ τ (n)
ρ . Si
le système dispose de ressources physiques de calcul parallèles suffisantes,
le temps de calcul de la boucle d’Euclide n’est plus dicté par la somme
des anneaux, mais uniquement par l’anneau de chaîne dominant (le plus
grand idéal) :
 
(i)
Ttotal = max CL-EEA (n) + O(k · ρ) (1.54)
i∈{1,...,ρ}

Cette parallélisation par décomposition CRT achève de lever le verrou de

la complexité du décodage des codes de Gabidulin sur les structures d’anneaux
finis, alliant la puissance théorique des modules libres développée dans les tra-
vaux fondateurs à une efficacité d’exécution adaptée aux exigences industrielles
du codage réseau.

12