pattirudonアルゴリズムのオーダー
このアルゴリズムのオーダーを調べます。
つまり、線形な遷移で決まっている疑似乱数で、状態から乱数は足し算で決まっているものとする。 このとき乱数値からseedを復元するアルゴリズムを考える。 ただし、簡単のため一個の乱数で見れるbit長を固定でkとする。
seedの長さをn bitとする。 このときアルゴリズムの計算時間は次の通り。
| アルゴリズム | 計算時間 |
|---|---|
| 愚直なアルゴリズム | Θ(2n) |
| pattirudonアルゴリズム | Ω(2n/2) |
ただしseedの候補を決めたとき、それが本当にseedかはΘ(1)時間でできるものと仮定する。
ここにΘ(f(n))はちょうどf(n)のオーダー、Ω(f(n))は少なくともf(n)のオーダーを意味する。
説明
何個の乱数を見るかをlとする。最適なlを調べる。
seedから乱数値を決める足し算する前の値を得る写像をf: F_2^n -> F_2^(2kl)とする (1個の乱数ごとに2l bitあることに注意)。 探索しないといけないbit数はkl + dim(Ker f)である。 ここにklは足し算する前の値の片割れのbit数、dim(Ker f)はそれを決めたときのf(x) = aの解空間の次元。
次元公式よりdim(Ker f) = n - dim(Im f) ≦ n - 2klなため、
(探索しないといけないbit数) = kl + dim(Ker f) ≧ kl + max{n - 2kl, 0} = max {n - kl, kl}。
これが最小となるのはl = n / (2k)のときで最小値はn / 2。 よって(n / 2) bitの探索をしなければいけないため、計算量はΩ(2n/2)である。
