M系列

M系列（Mけいれつ、m-sequence;maximal length sequence）とは、ガロア体における線形漸化式が生成する数列(sequence)のうち最長の周期(maximal length)を持つもの。MLSと略されることがある。

必要十分条件

M系列となるための必要十分条件は、線形漸化式が原始多項式であることである。

特徴

ガロア体上の線形漸化式であることから、その周期はG(pⁿ)の場合pⁿ-1である。例えば2進16ビットの場合はG(2¹⁶)であるため2¹⁶-1=65535長の数列となる。

これは線形漸化式であることからある値の次の値は必ず一通りに定まること、また原始多項式であることからゼロはゼロになることより、ゼロを除くすべての要素が現れた段階で周期が終了するからである。

擬似乱数

重要な応用として擬似乱数列の生成がある。漸化式が原始多項式であることが必要充分条件となっていることから最長周期を数学的に確認することができる特徴がある。M系列を用いた擬似乱数生成法として、線形帰還シフトレジスタやメルセンヌ・ツイスタなどがある。

特に線形帰還シフトレジスタはハード的にもソフト的にも実装が容易で高速であることから広く利用されている。なお線形帰還シフトレジスタにおいては漸化式のことを帰還多項式という。また、帰還多項式が原始多項式ではない線形帰還シフトレジスタも存在する。

線形漸化式が差分方程式の解であることから、単体では暗号論的擬似乱数生成器にはならない。