Re: Re: Polynôme générateur

According to Emile  <emilemusyck@gmail.com>:
> Je devrais préciser ce que j'ai dit précédemment. Comme 2047 n'est pas
> premier, il n'est pas possible de réaliser un LFSR à séquence maximum
> avec 11 cellules binaires.

Ben si. Enfin dans tous les cas, la séquence générée par un LFSR est
périodique (puisque l'état est fini) et pour un LFSR à 11 "cellules"
cette période ne peut pas dépasser 2047 (il n'y a que 2048 états
possibles, et l'état nul est dans son propre cycle de longueur 1).
Il y a donc une période maximale réalisable, d'au plus 2047.

Il s'avère que cette période maximale réalisable vaut 2047. Pour obtenir
une telle séquence, il suffit que le polynôme correspondant soit
primitif (i.e. premier [on peut aussi dire irréductible, c'est pareil
dans ce cas] _et_ tel que X génère un cycle passant par tous les
inversibles). Il existe des polynômes primitifs à coefficients binaires
et de degré 11, par exemple celui dont on parle (G = X^11 + X^9 + 1).

Que 2047 ne soit pas premier implique qu'il n'est pas _automatique_
qu'un polynôme premier de degré 11 soit primitif. Mais ça ne veut pas
dire que c'est impossible. En fait, il y a précisément 186 polynômes
à coefficients binaires, de degré 11 et irréductibles. Sur ces 186
polynômes, 176 sont primitifs, et donc si on les utilise pour un LFSR
on obtient une période de longueur 2047, qui passe bien par tous les
états non nuls possibles.

Sur les 10 autres, il y en a deux qui font des périodes de longueur 23 :

   X^11 + X^9 + X^7 + X^6 + X^5 + X + 1
   X^11 + X^10 + X^6 + X^5 + X^4 + X^2 + 1

ces deux polynômes découpent les 2047 états non-nuls en 89 cycles
disjoints de longueur 23. Quand on les utilise pour un LFSR, l'état
initial est sur un de ces cycles, et le LFSR reste dans le cycle en
question, avec une période de 23.

On notera que ces deux polynômes sont en fait deux fois le même, en
remplaçant X^i par X^(11-i). C'est tout-à-fait normal et attendu :
un LFSR avec un polynôme premier est réversible (puisque X est
inversible ; on peut multiplier par X mais aussi diviser par X)
donc en faisant tourner le LFSR dans l'autre sens, c'est comme si on
utilisait l'autre polynôme. Maintenant, si ça fait un cycle de longueur
23 dans un sens, ça fait forcément un cycle de longueur 23 dans
l'autre sens...

Il reste donc 8 polynômes premiers mais pas primitifs, qui font des
cycles de longueur 89 :

   X^11 + X^7 + X^6 + X + 1
   X^11 + X^8 + X^5 + X^4 + X^2 + X + 1
   X^11 + X^8 + X^7 + X^6 + X^5 + X^3 + X^2 + X + 1
   X^11 + X^10 + X^5 + X^4 + 1
   X^11 + X^10 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X^2 + X + 1
   X^11 + X^10 + X^9 + X^7 + X^6 + X^3 + 1
   X^11 + X^10 + X^9 + X^8 + X^6 + X^5 + X^4 + X^3 + 1
   X^11 + X^10 + X^9 + X^8 + X^7 + X^6 + X^5 + X^4 + X^3 + X + 1


Bon, au cas où, je me dois de préciser que les LFSR avec cycle de
longueur maximale, ça fleure bon la cryptographie de grand-papa. Il y a
un demi-siècle, on faisait du chiffrement symétrique avec un ou quelques
LFSR et en bidouillant les sorties selon une méthode qu'on croyait
finaude. Depuis, on s'est aperçu que c'est très difficile de faire
quelque chose de correct en partant dans cette direction. Les LFSR sont
des briques élémentaires utiles pour construire des schémas, mais il
faut plus que ça, sinon le schéma résultant ne sera qu'une vaste blague,
voire une fumisterie. Par ailleurs, la notion de "cycle de longueur
maximale" n'est en fait pas si importante que ça, dans ce genre d'usage.


	--Thomas Pornin