2-Terminologies_and_Basic_Recall.tex

   1 \subsection{Pseudorandom Galois Generators}
   2 F2-linear generators are a well-known PRNG class of and a special case of matrix linear recurrence modulo 2, where they are appropriate for low power and high speed requirement. However with the limitation of the shift register state, this generators enter to a finite and repeated state cycle and have a short period cycle. Because of that many hardware optimization are proposed to perform a good random and increase the period. A linear Random Number generator are defined following thous equations, where the first equation (1) $x_{t} = (x_{t,0}, . . . , x_{t,k−1})^{s}$ $\in F{^{k}}_{2}$ is the k-bit state vector at step n. the second equation (2) $y_{t} = (y_{t,0}, . . . , y_{t,w−1})^{s}$ $\in F{^{k}}_{2}$ is the w-bit output vector at step t, k and w are positive integers. Where, A is a $k*k$ transition matrix with elements in $F_{2}$, B is a $w*k$ output transformation matrix with elements in $F_{2}$, and $u_{i} \in [0, 1]$ is the output at step t:\\
   3 $x_{t} = A*x_{t−1}$ (1) \\
   4 $y_{t} = B*x{t}$ (2) \\
   5 $u_{t} = {\overset{w}{\underset{\ell= l}{\sum}}} \ y_{t,\ell -1} \ 2^{-\ell} = y_{t,0} \ y_{t,1} \ y_{t,2}\ · · · $ (3) \\
   6
   7 The characteristic polynomial of the matrix A is $x_{t} = a_{i}x{t-1} \ + \ · \ · \ · \ + \ a_{k}x_{t-k}$
   8
   9
  10 \subsection{Discrete Dynamics}