$F_2$ 上の線形生成器

$n \ge 1$ とし、$A$ を $\mathbb{F}_2$ の元を成分とする $n$ 次正方行列とする。状態集合 $S = \mathbb{F}_2^n$、遷移 $T(x) = Ax$ の生成器を $\mathbb{F}_2$ 上の線形生成器という。次の 2 つが代表的である。

• 線形帰還シフトレジスタ（LFSR）: ビットの列を漸化式 $b_{k+n} = \gamma_{n-1}b_{k+n-1} + \cdots + \gamma_0b_k$（$\gamma_i \in \mathbb{F}_2$）で作る。状態は $(b_k, \ldots, b_{k+n-1})$。
• xorshift: 状態を $n$ ビットの整数とみて、「左に $s$ ビットずらしたものとの XOR」「右に $s$ ビットずらしたものとの XOR」を何回か合成する。左シフトの行列を $L$、右シフトの行列を $R$ とすると、これらは $I + L^s$、$I + R^s$ という行列の積である。