線形帰還シフトレジスタ（せんけいきかんシフトレジスタ、）は、入力ビットが直前の状態の線形写像になっているシフトレジスタである。値域が単一のビットとなる線形写像は、XORおよびXORの否定だけである。したがって、線形帰還シフトレジスタとは、その値を構成するビット列の一部の排他的論理和を入力ビットとするシフトレジスタである。LFSR の初期値をシードと呼ぶ。レジスタの動作は決定的であるため、レジスタが生成する値の列はその状態によって完全に決定される。同様に、レジスタの取りうる状態は有限個であるため、最終的に周期的動作になる。しかし、帰還関数をうまく設定したLFSRは乱数のようなビット列を生成し、その周期も非常に長い。LFSRの用途としては、擬似乱数生成、擬似ノイズ生成、高速デジタルカウンタ、白色化などがある。LFSR にはハードウェアによる実装もソフトウェアによる実装もある。LFSRで、次の入力ビットに影響を与えるビットを「タップ (tap)」と呼び、それらの位置を列挙したものをタップシーケンスと呼ぶ。図では、タップシーケンスが [16, 14, 13, 11, 0] である。タップは順次XORされ、その結果が左端にフィードバックされる。LFSRの生成するビット列は、2進数やグレイコードと見なすことができる。LFSRのタップシーケンスは2を法とする多項式で表せる。つまり、多項式の各項の係数は1か0である。これを帰還多項式あるいは特性多項式と呼ぶ。例えば、図のようにタップが16番目、14番目、13番目、11番目にあるとき、帰還多項式は次のようになる。最後に1があるが、これはタップとは対応していない。これは、最初のビットへの入力に対応している（つまり、"x" であり、1と等価である）。各項のべき乗部分はタップ位置を表していて、左端から何番目かに対応している。左端は常に入力、右端は常にタップとして連結する。最長LFSRを構成する多項式（タップシーケンス）の性質を以下に示す。C/C++ のコーディング例を以下に示す。このコードでは、左端ビットが1番目の位置である。フランス人数学者エヴァリスト・ガロアの名を冠したガロアLFSRは、通常のLFSRと同じビット列を生成できる別の構成である。ガロアLFSRでは、タップでないビットはクロック毎に次のフリップフロップにシフトされる（普通のLFSRと同じ）。タップの場合、新たな出力と前のビットの値をXORしたものを格納する。通常のLFSRと同じ出力シーケンスを得るには、ビット順序を逆にする（図参照）。そうしないとシーケンスが逆転する。なお、LFSRの内部状態は同じである必要はない。図に示したガロアLFSRは、上の図で示したフィボナッチLFSRと同じ出力となる。以下は32ビットの最長ガロアLFSRをC言語およびC++で実装したものである（unsigned int は32ビットと仮定）。次のコードは、図にある16ビットの例である。LFSRはハードウェアでも実装できるため、高速な擬似乱数生成が必要な場面で便利である（直接シーケンス・スペクトラム拡散無線通信など）。レーダーは、LFSRを使って送信波と受信波の時間差を測定し、反射体までの距離を判定するものがある。グローバル・ポジショニング・システムは、LFSRを使って高精度な相対時間オフセットを示すシーケンスを高速に転送する。ファミリーコンピュータはサウンドシステムの一部としてLFSRを装備している()。コンピュータのインデックスやフレーム指示位置は機械可読である必要がある。そこで順に増えていく2進数でなくてもよい場合、LFSRの周期的シーケンスを分周器やカウンタとして使うことができる。LFSRカウンタは、通常の2進カウンタやグレイコードカウンタよりもフィードバック論理回路が単純で、より高速に動作させることができる。ただし、LFSR全体が0にならないよう保証する必要があり、例えば初期状態のプリセットが必要である。上の表はLFSRの最長周期が記してある。必要な周期よりも長い周期のLFSRに状態をスキップする論理回路を付加することで、任意の周期のカウンタを得ることができる。LFSRは、（特に軍事用途で）ストリーム暗号の擬似乱数生成器として使われてきた。これは機械式でも電子回路でも構成が簡単で、周期が長く分布が一様なためである。しかし、LFSRは線形システムであるため、暗号解読は比較的容易である。平文と対応する暗号文がわかっているとき、システムの使用するLFSRの出力を再現でき、Berlkamp-Massey法を使って最小サイズのLFSRを構築でき、容易に暗号文を復号できるようになる。LFSRに基づく暗号におけるこのような問題への対策として、一般に以下の3つの手法がある。LFSRに基づくストリーム暗号としては、GSM携帯電話で使っている A5/1 や A5/2、Bluetooth で使っている E0、 などがある。A5/2 は既に破られており、A5/1 と E0 も非常に弱いと言われている。0や1が連続すると、シンボルの区切りがわからなくなる危険性があるため、線形帰還シフトレジスタを使ってビットストリームを無作為化することが多い。この無作為化は受信側で復調後に除去される。LFSRと転送シンボルストリームが同じレートで動作する場合、この技法をスクランブリングと呼ぶ。LFSRの方がシンボルストリームよりずっと高速に動作し、信号送信時の帯域幅を拡張させる場合、これを直接シーケンス・スペクトラム拡散と呼ぶ。LFSRによるスクランブリングは暗号化ではなく、解読には、一般的な暗号において必要な困難は全く無い。LFSRを使っているデジタル放送システム:その他のLFSRを使っているデジタル通信システム:

出典:wikipedia