疑似ランダムビット生成
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/11 19:42 UTC 版)
「原始多項式」の記事における「疑似ランダムビット生成」の解説
GF(2) 上の原始多項式は，線形帰還シフトレジスタ(LFSR)を用いた疑似ランダムビット生成に利用できる．レジスタ長が n のLFSRの周期は最長で 2n - 1 であるが、全ての最長周期のLFSRは原始多項式を使って構築できる． 例えば，原始多項式 x10 + x3 + 1 が与えられたとき，まずユーザが決めた10ビットのシード（全てが0であるものを除く）から始める．右から順に1番目のビット，2番目のビット，...，10番目のビットとする．ここで、シードはランダムに選ばれている必要はないが，ランダムでもよい．次に，10番目と3番目のビットの排他的論理和を計算し，これを0番目のビットとする．そして，10番目のビットを出力するとともに、シードのビットを１つずつ左へずらす。つまり、9番目のビットを10番目のビットに、8番目のビットを9番目のビットに、と順にずらして0番目のビットを1番目とする．このプロセスを繰り返すことにより，長さ 210 - 1 = 1023 のビット列を生成できる． 一般に，GF(2) 上の m 次の原始多項式を用いると，このプロセスで周期が2m - 1 である疑似ランダムなビット列を生成できる．
※この「疑似ランダムビット生成」の解説は、「原始多項式」の解説の一部です。
「疑似ランダムビット生成」を含む「原始多項式」の記事については、「原始多項式」の概要を参照ください。
ウィキペディア小見出し辞書の「疑似ランダムビット生成」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 疑似ランダムビット生成のページへのリンク
