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

According to Michelot  <mhostettler@voila.fr>:
> Peut-on SVP l'appliquer simplement au polynôme k(X) qui fait une
> période de longueur 23 :
> 
> k(X) =  X^11 + X^9 + X^7 + X^6 + X^5 + X + 1
> 
> X^23 divisé modulo 2 par k(X) donne un reste égal à 1 (mais... votre
> phrase ne voudrait pas dire cela !)

Oui, c'est ça.

Ce que je veux dire, c'est que si on travaille modulo un polynôme
irréductible P de degré 11, alors l'ordre de X (la plus petite
valeur de r > 0 telle que X^r = 1 mod P, i.e. P divise X^r-1) est
soit 23, soit 89, soit 2047. Si on calcule X^23 et X^89 modulo P
et qu'on ne trouve 1 dans aucun des cas, alors c'est que l'ordre de
X est 2047, ce qui veut dire que le polynôme P est primitif.

Dans le cas de :

   P =  X^11 + X^9 + X^7 + X^6 + X^5 + X + 1

alors on a :

   X^23 = (X^12 + X^10 + X^7 + X^4 + X^3 + X^2 + X + 1) * P + 1

donc X^23 = 1 mod P. X est donc d'ordre 23 modulo P, et donc n'engendre
pas les 2047 inversibles modulo P, donc P n'est pas primitif.


	--Thomas Pornin