Lagged Fibonacci 法

Lagged Fibonacci 法︵ラグ付フィボナッチ法︶は擬似乱数生成法の1つ。この手法は標準的な線形合同法を改善する事を目的としており、フィボナッチ数の生成法を元にしている。

フィボナッチ数列は以下の漸化式により表現される。

$S_{n}=S_{n-1}+S_{n-2}$$S_{n}=S_{n-1}+S_{n-2}$
つまり、数列の前二項の和が次の項になる。これは以下のように一般化できる。

$S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},\quad 0<j<k$$S_{n}\equiv S_{n-j}\star S_{n-k}{\pmod {m}},\quad 0<j<k$
ここで、★演算子は一般的な二項演算子を表し、新しい項は以前の何らかの二項を演算して得られる。★演算子は加算にも減算にも乗算にもビット単位の排他的論理和にもなる。m は通常2の累乗︵m = 2^M︶で、2³² か2⁶⁴ がよく使われる。この種の生成法の理論はかなり複雑であり、j と kにより乱数を選ぶのは容易い事ではないだろう。また、この生成法は初期化の仕方にとても敏感な傾向もある。

この手法にはサイズ kの領域を必要とする︵最後の k個の要素を覚えておく︶。

二項演算として加算を行った場合、この方法は﹁加算 Lagged Fibonacci 法︵ALFG︶﹂となる。乗算を使えば﹁乗算 Lagged Fibonacci 法︵MLFG︶﹂となり、XORを使うと﹁2タップ一般化帰還シフトレジスタ︵GFSR︶﹂となる。メルセンヌ・ツイスタ法はGFSRの一種である。GFSRは線形帰還シフトレジスタ︵LFSR︶とも関連がある。

Lagged Fibonacci 法の性質

Lagged Fibonacci 法の最大周期は、二項演算として加算か減算を使った場合は (2^k − 1) × 2^M − 1 となり、XOR を使った場合は (2^k − 1) となる。乗算を使うと (2^k − 1) × 2^M − 3 となり、加減算を用いた場合の 1/4 になる。

最大周期を達成するには、多項式

y = x^k+ x^j+ 1

は modulo 2 の整数において原始的でなくてはならない。この条件を満たす jと kの組は文献に記されている。有名なものとしては、次のようなものがある︵(j, k) の順で記してある︶。

(7,10), (5,17), (24,55), (65,71), (128,159) [1]

(6,31), (31,63), (97,127), (353,521), (168,521), (334,607), (273,607), (418,1279) [2]

The Art of Computer Programming の volume 2 の28ページには、以下のようにその他の jと kの組も記されている︵既に上で示したものは太字にしてある︶。

(1,2), (1,3), (2,3), (1,4), (3,4), (2,5), (3,5), (1,6), (5,6), (1,7), (6,7), (3,7), (4,7), (4,9), (5,9), (3,10), (7,10), (2,11), (9,11), (1,15), (14,15), (4,15), (11,15), (7,15), (8,15), (3,17), (14,17), (5,17), (12,17), (6,17), (11,17), (7,18), (11,18), (3,20), (17,20), (2,21), (19,21), (1,22), (21,22), (5,23), (18,23), (9,23), (14,23), (3,25), (22,25), (7,25), (18,25), (3,28), (25,28), (9,28), (19,28), (13,28), (15,28), (2,29), (27,29), (3,31), (28,31), (6,31), (25,31), (7,31), (24,31), (13,31), (18,31), (13,33), (20,33), (2,35), (33,35), (11,36), (25,36), (4,39), (35,39), (8,39), (31,39), (14,39), (25,39), (3,41), (38,41), (20,41), (21,41), (5,47), (42,47), (14,47), (33,47), (20,47), (27,47), (21,47), (26,47), (9,49), (40,49), (12,49), (37,49), (15,49), (34,49), (22,49), (27,49), (3,52), (49,52), (19,52), (33,52), (21,52), (31,52), (24,55), (31,55), (7,57), (50,57), (22,57), (35,57), (19,58), (39,58), (1,60), (59,60), (11,60), (49,60), (1,63), (62,63), (5,63), (58,63), (31,63), (32,63), (18,65), (47,65), (32,65), (33,65), (9,68), (59,68), (33,68), (35,68), (6,71), (65,71), (9,71), (62,71), (18,71), (53,71), (20,71), (51,71), (35,71), (36,71), (25,73), (48,73), (28,73), (45,73), (31,73), (42,73), (9,79), (70,79), (19,79), (60,79), (4,81), (77,81), (16,81), (65,81), (35,81), (46,81), (13,84), (71,84), (13,87), (74,87), (38,89), (51,89), (2,93), (91,93), (21,94), (73,94), (11,95), (84,95), (17,95), (78,95), (6,97), (91,97), (12,97), (85,97), (33,97), (64,97), (34,97), (63,97), (11,98), (87,98), (27,98), (71,98)

小さい数であるほど周期が小さい点には注意する︵最初の乱数が再び現れるまでにほんの少しの乱数しか現れない︶。

乱数種の k個の値のうち最低でも1つは奇数にする必要がある。

Lagged Fibonacci 法の問題点

Lagged Fibonacci 法を初期化する方法はとても難しい問題である。Lagged Fibonacci 法の出力は初期条件にとても敏感であり、最初に統計的な欠陥があると、特別気をつけないとそれが周期的にやってくる。 他の潜在的な問題としては、この手法の数学的な理論はまだ完全ではないという点もあり、理論的にではなく統計的なテストにより信頼性を確認する必要がある。以上の理由に加え、高品質な疑似乱数列を生成し、フリーな実装例のあるメルセンヌ・ツイスタの存在により、より良い手法があるのにわざわざ自前で実装する価値は低いとされる傾向がある。

使用例

• Freeciv は乱数生成に {j = 24, k = 55} の Lagged Fibonacci 法を使っている
• Boost ライブラリは Lagged Fibonacci 法の実装を含んでいる
• MATLAB は rand() 関数に {j = ??, k = 32} の Lagged Fibonacci 法を使っている
• Oracle Database は DBMS_RANDOM パッケージ内で Lagged Fibonacci 法を使っている（Oracle 8 以上のバージョンのみ）

関連項目

• 線形合同法
• メルセンヌ・ツイスタ
• FISH (暗号)
• Pike (暗号)
• VIC cipher