Re: Polynôme générateur

According to Michelot  <mhostettler@voila.fr>:
> Tout polynôme pourrait-il être un polynôme générateur ?

Dans un groupe, on peut définir le sous-groupe engendré par un élément
comme le résultat de toutes les applications possibles de la loi de
groupe sur cet élément (en gros). Un polynôme, s'il fait partie d'un
groupe (par exemple, ce polynôme est inversible dans un certain anneau
de polynômes, et fait donc partie du groupe des polynômes inversibles
dans cet anneau, est alors mécaniquement générateur de son sous-groupe
engendré.

Là on peut se demander si ce sous-groupe engendré couvre tout le
groupe englobant, ou seulement une sous-partie stricte.

Il convient de préciser les termes de la question, ça devient trop flou.


Un cas courant dans certaines branches de la cryptographie est de
s'intéresser aux anneaux de polynômes (à coefficients dans un corps fini
donné) qui résultent du quotientage de l'anneau (brut) des polynômes par
un polynôme donné.

Soit K un corps fini. Un polynôme P à coefficients dans K est une
suite presque nulle d'éléments de K, notée comme ceci :

   P = \sum_{i=0}^\infty p_i X^i

où les p_i sont des éléments de K. La condition "presque nulle"
signifie qu'à partir d'un certain rang, les p_i sont tous égaux à
zéro. On peut donc définir le "degré" d'un polynôme, qui est le
rang du dernier coefficient non-nul. Autrement dit, on dit que P
est de degré n is p_n est non nul, mais p_j = 0 pour tout j > n.
Ceci couvre tous les polynômes sauf le polynôme nul dont tous les
coefficients sont nuls, et dont on dit conventionnellement qu'il
est de degré 0. Un polynôme "constant" est un polynôme de degré
zéro (p_i = 0 pour tout i >= 1).

On peut définir des opérations d'addition, soustraction, multiplication
et division euclidienne sur les polynômes, comme on ferait sur les
entiers. D'ailleurs, si on implémente ces opérations, ça ressemble
beaucoup à ce qu'on ferait pour implémenter des calculs sur des nombres
entiers, sauf qu'il n'y a pas de "retenue" à propager. Cela forme un
anneau, noté K[X] ("anneau des polynômes à coefficients dans K").

Comme il y a division euclidienne (avec quotient et reste), on peut
parler de divisibilité (quand le reste est nul) donc de polynôme premier
(divisible seulement par lui-même et par les polynômes constants non
nuls). On peut aussi définir des anneaux de polynômes modulaires, modulo
un certain polynôme de degré n >= 1. Plus précisément, si Q est un
polynôme de degré n >= 1 (donc Q n'est pas constant, donc pas nul non
plus), alors on définit l'anneau K[X]/Q qui contient les polynômes de
degré 0 à n-1, et où toutes les opérations sont réduites modulo Q (i.e.
on fait le calcul sur des polynômes bruts dans K[X], puis on fait une
division euclidienne par Q, et on ne garde que le reste, de degré
strictement inférieur à n par définition de cette division).

Il y a dans K[X]/Q des éléments inversibles ; ce sont les polynômes U
pour lesquels il existe un polynôme V tel que U*V = 1 mod Q. Les
inversibles forment un groupe multiplicatif, noté K[X]/Q*. Chaque
élément de ce groupe génère un sous-groupe (à partir de l'élément P, on
considère 1, P, P^2, P^3, etc... et les inverses de tous ces éléments).
Je note <P> le groupe multiplicatif engendré par P. Si ce sous-groupe
est égal à K[X]/Q* en entier alors on dit que l'élément P est un
_générateur_ du groupe des inversibles.

Si Q est un polynôme premier alors K[X]/Q est un corps. Cela revient à
dire que K[X]/Q* contient tous les polynômes de K[X]/Q sauf le polynôme
nul.

Si K est un corps à k éléments, alors K[X]/Q contient k^n éléments. Si
Q est premier alors K[X]/Q* contient k^n-1 éléments. Si P est un
inversible alors le cardinal de <P> divise celui de K[X]/Q*. Si
k^n-1 est un nombre entier premier, alors <P> ne peut être égal qu'à 1
(si P = 1) ou k^n-1 (dans tous les autres cas). Dans cette situation,
tous les polynômes inversibles sauf 1 sont générateurs du groupe des
inversibles.


En cryptographie, ces choses ont plusieurs usages. Le cas traditionnel
est celui des registres à décalage à rétroaction linéaire (LFSR en
anglais). Un LFSR contient n bits. À chaque tour, on décale tous ces
bits d'un cran vers la gauche, ce qui fait "tomber" un bit à gauche, et
crée un trou à droite. On comble le trou en calculant un "ou exclusif"
(le fameux XOR) de certains des bits du registre avant décalage, dont
(en général) celui qui est tombé.

On peut faire correspondre le LFSR à un anneau K[X]/Q. On considère K
le corps à deux éléments (0 et 1 ; l'addition sur ce corps est
précisément le XOR). On considère Q = X^n + \sum_{i=0}^{n-1} q_i X^i
tel que q_i = 1 si le bit numéro i rentre dans le XOR du LFSR, 0
autrement. C'est un polynôme de degré n. On peut alors s'apercevoir
que faire tourner le LFSR d'un bit revient à considérer l'état du
registre comme un polynôme (chaque bit étant un coefficient) et à
multiplier ce polynôme par X (ou le diviser par X, ça dépend du sens
de numérotation, mais tout ça est isomorphe et je saute les détails).

Du coup, faire tourner le LFSR revient à partir d'un état P (le
polynôme correspondant à l'état initial) et à calculer PX, PX^2,
PX^3, etc... dans K[X]/Q.

_Si_ les conditions suivantes sont respectées :

  -- Q est un polynôme premier (donc K[X]/Q est un corps)
  -- X est générateur de K[X]/Q*
  -- l'état initial du LFSR n'est pas nul (il y a au moins un bit non
     nul dedans)

_alors_ on voit que le LFSR se balade sur tous les inversibles et
son état fait alors un grand cycle de taille 2^n-1, ce qui est le
plus grand qu'on puisse faire et qui est considéré comme une "bonne
chose" pour les usages traditionnels des LFSR.

Dans ces conditions, on dit que Q est un polynôme _primitif_.


> En quoi pourrait-on dire que G(x) = 1 + X^9 + X^11 est un polynôme
> générateur ?

Si on considère que K est le corps à deux éléments, alors le polynôme
G = X^11 + X^9 + 1 dans K[X] est primitif. Autrement dit, non seulement il
est premier (on ne peut pas trouver deux polynômes de K[X] U et V, tous
deux de degré 10 ou moins, tels que G = U*V) mais en plus le sous-groupe
engendré par X modulo G contient tous les 2047 polynômes non-nuls de
K[X] de degré 10 ou moins.

On peut imaginer dire que "G est un polynôme générateur" mais c'est un
abus de langage, le terme technique correct étant "primitif".

On notera que 2047 = 23 * 89 donc il n'est pas gagné d'avance qu'un
polynôme premier de degré 11 soit également primitif. C'est néanmoins
le cas pour le polynôme G ci-dessus. Un exemple de polynôme de degré
11 premier mais pas primitif est :

   R = X^11 + X^7 + X^6 + X + 1

K[X]/R est bien un corps, donc tous les polynômes non nuls de degré 10
ou moins sont bien inversibles modulo R, et en particulier le polynôme
P = X. Mais le groupe engendré par X est de taille 89 seulement. Donc
un LFSR qui utiliserait des bits de rétroaction aux positions 0, 1, 6
et 7 ferait un cycle de longueur 89 (pas toujours le même cycle de
valeurs, suivant l'état initial, mais quel que soit l'état initial il
reviendrait dessus en 89 étapes).


	--Thomas Pornin

PS : dans tout ça j'ai parlé du cas où K est un corps.
Traditionnellement on utilise le corps à deux éléments. Maintenant, ça
marche aussi avec d'autres corps finis, et d'ailleurs le quotientage par
un polynôme est une mécanique servant à fabriquer des corps finis. On
peut _aussi_ envisager le cas où K n'est pas un corps mais seulement un
anneau ; par exemple, si on envisage un LFSR où les éléments ne sont pas
des bits mais des chiffres décimaux (les chiffres de 0 à 9 forment un
anneau mais pas un corps). Les choses deviennent alors fichtrement plus
compliquées.