線形合同法数列が最大周期になる条件(ただし法が2のべきの場合) その2
線形合同法である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数列の性質
証明すべき命題
(s,a,b,2^k)で定義されるLCG数列が最大周期となる必要十分条件は以下の3つを全て満たすことである
- aが奇数
- bが奇数
- k > 1ならばa ≡ 1 (mod 4)
ただし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が奇数であることは最大周期であるために必要。
「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}が
- aが奇数
- bが奇数
- k > 1ならば、a ≡ 1 (mod 4)
を満たすならば、{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}が最大周期であることが証明された。
