Hatena::ブログ(Diary)

oupoの日記

2015-01-28

線形合同法数列が最大周期になる条件(ただし法が2のべきの場合) その2

11:57

線形合同法であるseedが0からいくつ進めたものかを得る その2 - oupoの日記の記事のアイディアを使ったら簡単な証明を得たので記す。

先の最大周期になる条件の証明はくどすぎた感があるので今回は簡潔に済ませる。

定義

  x_0 = s

  x_{n+1} = (a x_n + b) mod 2^k

で定義される数列{x_n}を(s,a,b,2^k)で定義されるLCG数列と呼ぶことにする。

この数列は、x_n = sとなる最小の整数n > 0がn = 2^kのとき最大周期であると呼ぶ。

また、a, b, 2^kが定まっている文脈において関数fを

  f(x) = (ax + b) mod 2^k

の意味で使う。

最大周期のLCG数列の性質

  • 0 <= i, j < 2^kかつi ≠ jならばx_i ≠ x_jである
  • 数列の項x_0, x_1, …, x_{2^k-1}には2^k個の整数0, 1, …, 2^k-1が一回ずつ現れる

証明すべき命題

(s,a,b,2^k)で定義されるLCG数列が最大周期となる必要十分条件は以下の3つを全て満たすことである

ただしk > 0とする。

s = 0としても一般性を失わないこと

上記の命題を証明するにあたって、s = 0の場合のみ証明すれば十分である。

このことは、2つの初項s, s'に対して(s,a,b,2^k)で定義されるLCG数列が最大周期ならば(s',a,b,2^k)で定義されるLCG数列も最大周期であることを言えばよい。

実際、(s,a,b,2^k)で定義されるLCG数列{x_n}が最大周期ならx_i = s'となるiが存在する。そこでy_n = x_{i+n}と定義すれば{y_n}は(s',a,b,2^k)で定義されるLCG数列に一致するが、これは最大周期となる。

以下s=0とする。

bが奇数であることの必要性

bが偶数なら{x_n}の各項はすべて偶数になり最大周期とならない。よってbが奇数であることは最大周期であるために必要。

aが奇数であることの必要性

aが奇数とするとf(0) = f(2^{k-1})となってfは単射とならないので、{x_n}は最大周期にならない。

「k > 1ならば、a ≡ 1 (mod 4)」の必要性

(0,a,b,2^k)で定義されるLCG数列{x_n}が最大周期と仮定する。

数列の漸化式より

  x_{n+2} = (a^2 x_n + (a + 1)b) mod 2^k

が得られる。

ここでnが偶数なら上の両辺は偶数である(∵ x_0 = 0とa + 1が偶数であることから帰納法)。

よって両辺を2で割って

  x_{n+2} / 2 = (a^2 (x_n / 2) + (a + 1)b / 2) mod 2^{k-1}

を得るので数列{x_{2n} / 2}は(0, a^2, (a + 1)b / 2), 2^{k-1})で定義されるLCG数列だと分かる。

法を2^{k-1}とするこのLCG数列は仮定により最大周期であるので(a + 1)b / 2は奇数でなければならない。(この部分で仮定k > 1を使っている。k = 1なら2^{k-1} = 1を法とするLCGは"加える数"が奇数である必要はない)

しかしa ≡ 3 (mod 4)なら(a + 1)b / 2は偶数となるのでa ≡ 1 (mod 4)でなければならない

十分性の証明

(s,a,b,2^k)で定義されるLCG数列{x_n}が

を満たすならば、{x_n}が最大周期なることを証明する。

kに関する帰納法による。

k = 1なら明らかである。

k > 1としてk - 1のとき成り立つとする。

すると{x_{2n} / 2}は(0, a^2, (a + 1)b / 2, 2^{k-1})で定義されるLCG数列なので帰納法の仮定によりこれは最大周期である。

よってx_{2i} / 2 = 0となる最小のi > 0は2^{k-1}なので、偶数iでx_i = 0を満たす最小のi > 0は2^kだと分かる。また奇数iに対してはx_iは奇数となるのでx_i = 0とならない。

したがって{x_n}が最大周期であることが証明された。

トラックバック - http://d.hatena.ne.jp/oupo/20150128/1422413849