Corps de Galois pour algorithme de Reed-Solomon

[invitef45cc474]

Salut tout le monde
Voilà je suis en mpsi et je bosse mon tipe. J'ai choisi de m'intéresser à l'algorithme de Reed-Solomon utilisé pour la réparation de données informatiques dans les systèmes RAID (pour la petit histoire, c'est ce qui est utilisé dans les fichiers PAR qui sont très utiles pour réparer des bouts de divx corrompus sur les newsgroups lol).

Bon j'utilise surtout ce document:
http://www.cs.utk.edu/~plank/plank/papers/CS-96-332.pdf

Il est assez complet, ça me permet de piger à peu près tout grâce à mon cours...
Mais ce qui me manque pour que mon tipe tienne debout, c'est des infos sur les corps de Galois. Vu que les "mots", c'est-à-dire les données dont on veut assurer la protection, sont de taille fixée, on doit utiliser un corps fini (ainsi les combinaisons linéaires des mots, qui permettent de retrouver des données perdues, sont aussi de la même taille). C'est pourquoi les corps de Galois entrent en jeu.
J'ai cherché un peu sur google (en anglais) et j'ai cru comprendre que pour une puissance donnée r d'un nombre premier p, il existe un unique corps de Galois. J'ai également à peu près compris la définition des deux lois (ça utilise des polynomes de degrés inférieurs à r, à coefficients entre 0 et p-1).
Mais ce qu'il manque cruellement dans ce document, c'est la raison profonde pour laquelle cela forme un corps; pourquoi les axiomes des corps sont vérifiés? (par exemple la distributivité de * sur +).
J'ai cru aussi comprendre que ça utilise des groupes cycliques...

Enfin bref, j'aimerais bien avoir des infos précises à ce sujet (que ce soit grâce à votre incroyable culture mathématique, ou grâce à un site). J'ai beau chercher et je tombe à chaque fois sur des articles qui partent dans des délires qui me dépassent lol

Merci d'avance
-----

[invite4793db90]

Salut,

je ne vais pas détailler la théorie de Galois proprement dite, car elle ne te servirais pas vraiment de toute façon.

Je vais plutôt te montrer comment construire un corps qui en contient un autre. Je suppose que tu connais les corps Z/pZ (p premier) et la notion d'ensemble quotient.

Un premier exemple: construction de C

Tu as déjà vu que C peut être construit en rajoutant une solution i de l'équation x²+1=0.
Une autre construction un peu plus algébrique est la suivante (mais celà revient quasiment au même):
dans R[X], X²+1 est un polynôme irréductible. Soit I l'ensemble de tous les multiples de X²+1: . On dit que I est l'idéal engendré par X²+1 et on le note (X²+1).
Ce qui est intéressant c'est que l'on va pouvoir quotienter R[X] par I: la relation d'équivalence est donnée par P~Q ssi P-Q I. Tu obtiens alors un ensemble sur lequel tu peux facilement récupérer la structure d'anneau. C'est l'ensemble des polynômes modulo X²+1. Il se trouve que c'est un corps, car X²+1 est irréductible sur R (c'est le théorème essentiel). Et il n'est pas difficile de montrer que cette ensemble est isomorphe à R[i]=C.

Construction de F_q

Pour construire un sur-corps de F_p=Z/pZ, il suffit d'appliquer la même méthode: se donner un polynôme P irréductible sur F_p (en utilisant par exemple le critère d'Eisenstein).
On forme le quotient F_p[X]/(P) et bingo, on obtient un corps. De plus, le théorème de l'élément primitif permet d'affirmer que le corps obtenu est isomorphe à F_p(a) où a est une racine de l'équation P(x)=0. Enfin, si le degré de P est r, l'extension F_p[X]/(P)=F_q contient p^r éléments et est unique à isomorphisme près.

Voili, je tâche de te trouver une doc sur les extensions de corps.

Cordialement.

PS: j'ai peut-être omis certains points de détail, mais le squelette général est celui-là.

[invite4793db90]

Une disussion sur la construction de F₄.

[invite4793db90]

... et un cours sur le sujet.

[A voir en vidéo sur Futura]

[invitef45cc474]

OK merci beaucoup, ça m'éclaire.
Maintenant, j'ai juste deux questions précises:

1) Pourquoi lorsque Q€R[X] est irréductible l'ensemble R[X]/Q est un corps ? (ce que tu appelles théorème essentiel)
enfin pour mon cas c'est pas R mais juste {0,1} vu que les opérations sont faites sur les bits.

2) Je note CG(2^w) le corps de galois à 2^w éléments muni de ses deux lois. On a CG(2)={0,1}
On définit CG(2^w) en l'identifiant à CG(2)[X]/Q où Q est un polynome irréductible dans CG(2)[X].
L'article dont j'ai donné l'adresse dit ensuite que X est générateur de CG(2^w), et qu'on peut donc écrire la liste ses éléments en calculant X^i mod Q, pour i allant de 0 à (2^w)-1.
Ouais bah là je pige pas pourquoi X est générateur...

Merci

[invite4793db90]

1) Pourquoi lorsque Q€R[X] est irréductible l'ensemble R[X]/Q est un corps ? (ce que tu appelles théorème essentiel)
enfin pour mon cas c'est pas R mais juste {0,1} vu que les opérations sont faites sur les bits.

Soit K un corps.
Clairement si Q=R.S avec R et S non constants, K[X]/(Q) ne peut être un corps, du fait de la présence de diviseurs de zéro. En effet, si R' (resp S') sont les classes de R et S modulo Q, on a R'.S'=0 (mod Q). Le fait que Q soit irréductible est donc nécessaire.

Supposons maintenant que Q soit irréductible et soit P K[X]/(Q): soit P' K[X] un représentant de P tel que deg(P)<deg(Q) (c'est bien entendu toujours possible, par division euclidienne). Puisque P' et Q sont premiers entre eux, d'après le théorème de Bézout, il existe U et V K[X] tels que UP'+VQ=1 et P admet donc un inverse modulo Q.