Knuth のアルゴリズム

本節で述べる Knuthによるアルゴリズム[8]は，

s_i=a s_i−1+cmodm

について，m = 2^k，amod 4 = 1, cmod 2 = 1 という仮定の下で，kが既知のときに，

x₀, x₁, x₂, . . .からa, c, s₀を計算するアルゴリズムである．より詳細に述べると，[8] には，下 の二つの問題を解くアルゴリズムが与えられている．なお，以下では k=h+l である．

問題A

入力：bs_i/2^lc (0≤i <2^l) 出力：a，c，s₀

問題B

入力：bs_i/2^lc (0≤i < N) 出力：a，c，s₀

問題Aについては，l >1に対して，O(2^l)ステップのアルゴリズム，問題Bについては，h≥2 に対して，O(k²2^2l/N²)ステップのアルゴリズムが与えられている．

5.4.1 問題Aのアルゴリズム

s_iの下位からl番目のビットをs^(l)_i と表記する．このとき，

s^(l)_i =bs_i/2^l−1cmod 2

である．なお，最下位ビットは下位から1番目のビットと呼ばれる．

問題Aのアルゴリズムでは，bs_i/2^lc (0 ≤ i ≤ 2^l) から，bs_i/2^l−1c (0≤ i ≤ 2^l−1) を求め ることを繰り返すことにより処理が進められる．このためには，bs_i/2^lc (0 ≤ i ≤ 2^l) から，

s^(l)_i =bs_i/2^l−1cmod 2 (0≤i≤2^l−1) が求められれば十分である．

補題 1 0≤t < kについて，

y_n+1^(t) =s_n+2t −s_nmod 2^k

とする．このとき，すべてのnについて y_n+1^(t) =a y_n^(t)mod 2^k

である．また，y_n^(t)は2^tの奇数倍である． ¤ 補題 2 1≤l < k−1について，以下を満たす定数b_l ∈ {0,1} が存在する．

s^(l)_n =s^(l+1)_n+2l−1 −s^(l+1)_n +b_lmod 2

¤ 補題2より，b_l が分かれば，bs_i/2^lc(0≤i <2^l) の最下位ビットから，s^(l)_i =bs_i/2^l−1cmod 2 (0≤i <2^l−1) が求められることが分かる．さらに，補題1より，

s_n+2l−1 ≡y^(l−1)_n +s_nmod 2^k

であり，かつ，y^(l−1)_n の下位からl番目のビットは1で，それより下位のビットはすべて0であ るから，

s^(l)_n+2l−1 = 1−s^(l)_n

であることが分かる．これらのことから，b_lが分かれば，bs_i/2^lc (0≤i <2^l) から，bs_i/2^l−1c (0≤i≤2^l−1) が計算できることが分かる．

bs_i/2^lc (0≤i≤2^l) が分かっているとき，l≥2ならば，b_l は以下の式によって計算できる ことが証明できる．

bs₀/2^lc −2bs₂l−1/2^lc+bs₂l/2^lc ≡2s^(l)₀ + 1 (mod 4) s^(l)₀ =s^(l+1)₂l−1 −s^(l+1)₀ +b_l mod 2

ただし，アルゴリズムの入力としてはbs₂l/2^lc が与えられないので，b_l を計算することができ ない．この場合は以下のように対処する．

• h= 1 の場合は，b_l は0でも1でもどちらでも良いことが証明できる．

• h≥2 の場合は，b_l= 0 とb_l= 1 の両方について処理を進める．

問題Aに対するアルゴリズムは以下の通りである．

1. h≥2 ならば，以下のステップをb_l= 0とb_l = 1の両方について実行する．それ以外の 場合，すなわち，h= 1 の場合は，b_l= 0 についてのみ実行する．

2. 0≤n <2^l−1について，

s^(l)_n =s^(l+1)_n+2l−1 −s^(l+1)_n +b_l mod 2

を用いて s^(l)_n を計算する．次に，x^(l)_2l−1 = 1−x^(l)₀ とする．lを1減らす．

3. l≥2 ならば，次の二つの式

bs₀/2^lc −2bs₂^l−1/2^lc+bs₂^l/2^lc ≡2s^(l)₀ + 1 (mod 4) s^(l)₀ =s^(l+1)_2l−1 −s^(l+1)₀ +b_l mod 2 により，b_lを計算してステップ2に戻る．

4. (x⁽¹⁾₀ , x⁽¹⁾₁ , x⁽¹⁾₂ ) が取り得る2通りの値(0,1,0)，(1,0,1)の両方について，

a = x₂−x₁

x₁−x₀ mod 2^k c = x₁−a x₀mod 2^k

を計算する．得られた値から与えられた入力が生成できるかどうかを確認する．

なお，このアルゴリズムは，入力について l= 1の場合はうまく動作しない．[8]では，この場 合の解法についても言及されている．

5.4.2 問題Bのアルゴリズムについて

問題Bについては，Nが小さいと非常に多数の解が存在する．今，

s⁰_n=s_n+bmod 2^k と定義すると，

s⁰_n+1=as⁰_n+ (c−(a−1)b) mod 2^k が成立する．このとき，s_min = min

0≤n<N{x_nmod 2^l}，s_max = max

0≤n<N{x_nmod 2^l} とすると，

−s_min ≤ b < 2^l−s_max ならば，0 ≤n < N について，bs⁰_n/2^lc = bs_n/2^lc が成立する．した がって，このようなbについて s⁰₀ =s₀+bmod 2^k を満たすs⁰₀ はすべて正しい解となる．

ところで，

y₀ =s₁−s₀mod 2^k

と定義すると，補題1から，すべてのnについて，

js_n 2^l k

= js₀

2^l k

+

¹aⁿ−1 a−1 ·y₀

2^l º

+²_nmod 2^h

が成立することが証明できる．ただし，²_nは0または1である．そこで，問題Bのアルゴリズ ムは，以下の二つの手続きによって構成される．

1. 与えられた入力から(a, y₀)を求める．

2. (a, y₀)から，与えられた入力と同一の系列を生成できるs₀の範囲を求める．

(a, y₀)を求める手続きでは，まず，2^t+ 1< N なる最大のtについて，可能なすべての y₀^(t) = s₂t −s₀mod 2^k を計算し，

y_n^(t) = (1 +a^2t−1)y^(t−1)_n mod 2^k

によってtを1ずつ減らすことにより，最終的にy₀ =y₀⁽⁰⁾を得る．なお，この処理中に，各t について，

$ y_n^(t)

2^l

%

+κ^(t)_n = js_n+2^t

2^l k

− js_n

2^l k

mod 2^h

³

κ^(t)_n は0または1

´

を用いて可能なy₀^(t) の絞り込みが行われるが，h= 1のとき，この式は常に成り立つので，絞 り込みには利用できない．したがって，このアルゴリズムではh≥2が仮定されている．

5.4.3 考察

本節で述べたKnuthのアルゴリズムは，非常に興味深いものであるが，NIST SP800-22 の LCG に適用するという観点からは，以下のような問題点が挙げられる．

• 線形合同式の法が2のべき乗の場合にのみ有効なアルゴリズムであること．

• ステップ数が，擬似乱数列として出力されない各s_iのビット数乗に依存すること．また，

問題Bのアルゴリズムでは，擬似乱数列として出力される各s_iのビット数が2以上であ ることが仮定されていること．