Discussion :

[Tymk]

Lorsque l'on cherche a exprimer par exemple, a^257 :

Etant donné que le tabeau des éléments de GF(256) ne contient que 256 éléments on recommence au début mais on "saute" l'élément nul :

a^257 = a²

Quelqu'un peut m'expliquer pourquoi on fait ça ?
(J'imagine bien que l'élément nul à tendance à fausser les calculs mais je n'en saisie pas l'interprétation fondamentale)

[Matthieu Brucher]

on a a^256 = 1, normalement non ?

[Tymk]

Justement je sais pas trop.

GF(256) contient 256 éléments à savoir (0,1,a,a²,....,a^254)
le tout est de savoir si a^255 = 0 ou 1

Tu aurais tendance à dire qu'il vaut 0 et moi 1. Mais je ne suis pas très sûr de moi.

[DrTopos]

L'explication est très simple et de niveau élémentaire. Il suffit de se souvenir que dans un groupe fini l'ordre de tout élément divise l'ordre du groupe (Ceci résulte facilement du théorème de Lagrange sur le cardinal des sous-groupes).

Or, dans le corps GF(256), le groupe (multiplicatif) des éléments non nuls a 255 éléments. Il en résulte que tout élément x non nul de GF(256) vérifie x^255 = 1, donc bien entendu (en multipliant par x^2), x^257 = x^2.

Toutefois, il peut exister un exposant k plus petit que 255, tel que x^k = 1. Le plus petit d'entre eux (strictement positif) s'appelle justement l'ordre de x. Ce qui est intéressant est qu'il existe malgré cela toujours des éléments d'ordre (multiplicatif) n-1 dans un corps à n éléments. Ceci résulte d'un théorème pas très difficile qui dit que le groupe des inversibles d'un corps fini est toujours cyclique. C'est un tel élément qui a été appelé 'a' dans les post précédents.

J'ai eu l'occasion il y a quelques temps de discuter de ces questions sur DVP, et j'ai écrit un petit papier d'explications générales qu'on peut trouver ici.

[progfou]

Je regarde ce document, et je tombe, en page 3, sur :

On voit que ce n'est pas un corps au fait que 2 n'est pas inversible. On verra plus loin que cette construction
donne un corps seulement quand on la fait avec un nombre premier.

Ca signifie que l'anneau Z/16, qui serait en quelque sorte représentatif du "calcul" hexadécimal, n'est pas un corps ?

[DrTopos]

Ca signifie que l'anneau Z/16, qui serait en quelque sorte représentatif du "calcul" hexadécimal, n'est pas un corps ?

Il est certain que Z/16 n'est pas un corps. par exemple l'équation 2x = 1, n'a aucune solution dans cet anneau, alors que 2 n'est pas nul dans Z/16. En effet, quelle que soit la valeur qu'on donne à x, 2x ne peut valoir que l'une des valeurs suivantes: 0, 2, 4, 6, 8, 10, 12, ou 14.

Par ailleurs, est-ce que Z/16 est représentatif du calcul hexadécimal ? Non, car le calcul hexadécimal c'est le calcul dans Z (ou dans N) en base de numération 16, et non pas le calcul dans Z/16.

Ceci dit, si on examine les instructions d'un processeur réel (comme le pentium), on voit que le calcul qu'implémentent les instructions arithmétiques est exactement celui de l'anneau Z/2^32. (ou Z/2^16, dans le cas d'un ancien processeur comme le 8086). C'est donc bien dans cet anneau étrange: Z/2^n, qu'on calcule avec nos processeurs.

Si on fait quelques expériences en langage C avec le type 'int', on va constater, que les opérations arithmétiques sont bien celles de Z/2^32, et non pas celles de Z.

Il y a donc une tromperie fondamentale dans l'informatique qui veut nous faire croire que des nombre représentés par des mots de 16 ou de 32 bits sont des entiers, c'est à dire des éléments de l'anneau principal Z. Au contraire, ce sont des éléments de Z/2^32, qui est très loin d'être un anneau principal (en encore moins un corps évidemment). Il n'est même pas intègre. En fait il s'agit d'un anneau local (un seul idéal maximal) et son intérprétation correcte est très très loin de la notion d'entier. Géométriquement, il s'interprèterait plutôt comme un anneau de germes de fonctions. En tout cas, il ne vérifie aucune des propriétés qu'on est en droit d'attendre des entiers: division euclidienne, Bézout, existence et unicité de la décomposition en facteurs irréductibles etc... C'est donc une arnaque fondamentale qui se fait jour quand on arrive à ce qu'on appelle pudiquement le dépassement de capacité, mais qui n'est à mon avis qu'une indigence lamentable dans le design des ordinateurs.

Maintenant, le corps de Galois GF(2^n), lui est bien un corps, mais la multiplication n'y est pas celle du processeur Pentium. Les éléments de GF(2^n) sont des polynômes à coefficients dans Z/2 (qui se calculent modulo un polynôme irréductible de degré n), et non pas des éléments de Z/2^n. Le même ensemble à 2^n éléments peut être muni de plusieurs structures d'anneaux différentes (dont certaines sont des corps).