talk/regth5demo.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 \begin{enumerate}
  12 \item Construction d'un polynôme $b \in (\F_{p})_{r-1}(x)$ et d'une fonction
  13 $T: (\F_{p})_{r-1}(x) \rightarrow  \F_p$ t.q. $T(b.x^n)=a_n$ ({\sc Lemme}~6)
  14 \item Comme $x^{p^r-1}\equiv 1 \mod Q(x)$, d'après 1. la période de $a_n$ est au plus $p^r-1$ (l.~290)
  15 \begin{itemize}
  16 \item $a_{n+p^r+1} \equiv T(b.x^{n+p^r+1}) \equiv  T(b.x^{n}x^{p^r+1}) \equiv a_n$.
  17 \end{itemize}
  18 \item Si la période était inférieure à $p^r -1$, alors $Q(x)$ ne serait pas
  19 primitif (l. 296)
  20 \end{enumerate}