talk/regth5.tex

   1 \begin{theorem}[Théorème 5]
   2 Soit $p$ premier,  $q_0, \dots , q_{r-1} \in \F_p$  tels que
   3 $Q(x) = x^r - q_{r-1} x^{r-1} - \dots - q_1 x - q_0$ est primitif
   4 sur $\F_p$ et soit
   5 $a_0, \dots, a_{r-1}$  une  graine différente du vecteur nul.
   6 Le générateur à base de registres à décalage linéaires engendre une suite de
   7 période $p^r-1$.
   8 \end{theorem}
   9
  10
  11
  12 \begin{exampleblock}{Analyse de l'exemple de la Figure~5}
  13 On a $p=3$, $r=4$, la graine $1,0,0,0$ n'est pas nulle.
  14 Il suffi(rai)t de démontrer que
  15
  16 \begin{enumerate}
  17 \item  $Q(x) = x^4 - 2 x^{3} - 1 \equiv x^4 + x^{3} + 2$ est irréductible
  18 (facile)
  19 \item  chaque  élément de
  20 $
  21 (\F_{p})_{r-1}(x)
  22 $
  23 peut s'écrire sous la forme $x^i$ modulo $Q(x)$, $0 \le i \le p^r-2$ (long, mais vrai)
  24 \end{enumerate}
  25
  26 La période d'un tel générateur est donc $3^4-1=80$.
  27 \end{exampleblock}
  28
  29