全射性は、行列の掃き出しを行えばよい。が、19937次正方行列の掃き出し は意外に計算機でも大変である。
形式冪級数体の格子の幾何を用いると効率よく計算できる([1])。
定理 7.3. 擬似乱数が最大周期性を持つとする。0でないs0 ∈ Sを一つ取り、
{e1, e2, . . . , ev, w(s0)}が生成するF2[t−1]加群をL⊂Fv とする。すると w(S) =L∩Av
が成立する。
証明. s0からm回動いた状態をsmとすると
w(sm) =t−mw(s0)の負冪の項を除いたもの である。よって
w(sm)⊂L.
w(sm) ∈ Avは自明。最大周期の仮定よりmを動かすとw(sm)はw(S)− {0} の元を全てつくす。よって⊂が言えた。
逆に、F2線形空間としての直和
L :=w(S) +F2[t−1]< e1, e2, . . . , ev >
はt−1倍について閉じている。(右の項は<>の中身を基底とするF2[t−1]加群。) よってF2[t−1]加群。w(s0)∈w(S)よりL ⊃L。両辺とAv の共通部分をとる と⊃が言える。
Fvの元の有限集合にたいし、そのノルムをその中の元のノルムの最大値と 定義する。
LのF2[t−1]基底Bのなかで、ノルムが最小のものを最短基底とよぶ。
定理 7.4. Lの最短基底のノルムは2−k(v)である。
証明のためいくつか準備をする。
定義 7.5. F2[t−1]格子L⊂Fvに対し、各Lの元をそれを中心とする半径rの 球に置き換えると全空間Fvを覆うとき、Lの被覆半径はr以下であるという。
（そのようなrの最小値をLの被覆半径という。）
補題 7.6. 最大周期の仮定のもとで、出力が少なくともk次元均等分布すると いうことと、Lの被覆半径が2−k−1以下であることとは同値である。
証明. 被覆半径が2−k−1以下だとしよう。いま、任意のkvビットパターンを考 える。これを冪級数化して（k項めで打ち止めになっている）Avの元xをつく る。Lの元xで誤差2−k−1でxが近似できる。すると自動的にx ∈Av、すな わち
x ∈L∩Av,|x−x| ≤2−k−1.
このときxのk項目まではxに一致している。先の定理によりx ∈w(S)。す なわち、いつかは与えられたkvビットパターンが現れる。よってk次元均等 分布している。
逆に、任意のkvビットパターンを実現できるということは、L∩Avの各元 を半径2−k−1の球で膨らませるとAvを覆うということに他ならない。F2線形 空間としての直和
Fv =Av+F2[t−1]< e1, e2, . . . , ev >
とL ⊃F2[t−1]< e1, e2, . . . , ev > を用いれば、Lの被覆半径は2−k−1以下とわ かる。
証明. (定理7.4の証明) 上の補題により、
最短基底のノルムが2−k以下⇔Lの被覆半径が2−k−1以下 を言えばよい。よって、
ノルムが2−k以下の基底Bが存在⇔Lの被覆半径が2−k−1以下 を言えばよい。左から右をしめす。Bは基底であり、Lは最大次元格子である からF 上BはFvを生成する。よって任意のベクトルx∈Fvは
x=
i
aibi, ai ∈F, B ={b1, . . . , bv}
と書ける。aiに最も近いF2[t−1]の元をαiとすれば、|ai−αi| ≤1/2で
||x−
i
αibi||=||
i
(ai −αi)bi|| ≤1/2||B|| ≤2−k−1 であり、右が言えた。
右から左を言う。原点中心で半径2−kの球を考える。まず、この球に入るLの 点であってFvの基底になるものがあることを示す。ei = (0, . . . ,0,1/t,0, . . . ,0) とおく。被覆半径の定義から、
||tk+1ei −i|| ≤2−k (7) なるi ∈Lがある。すると
||i||= 2−k
であるから、1, . . . , vが一次独立であることを示せばよい。(7)より tk+1ei ≡i modtk+1,
よって modtk+1で見てiは(0,0, . . . ,0, tk,0, . . . ,0)に一致する。
今iたちが一次従属であったとして、非自明な一次結合を
i
aii = 0, ai ∈F
とおく。t冪と定数を適当に賭けることでai ∈Aで、どれか一つは定数項が1 としてよい。a1がそれであるとしても一般性を失わない。すると、上の等式を mod tk+1 でみると、左辺は(tk,0, . . . ,0)となり、矛盾である。
こうして、中心0半径2−kの球の中のLの点で、一次独立なものがv本とれ ることがわかった。そういったものの中で、ノルムの和が最小のものBをと る。これがLの基底となることを示そう。Lの任意の元xをとる。これがBの 元のF2[t−1]係数一次結合でかければよい。Bの元のF 係数一次結合でxを書 く。BのはるF2[t−1]格子の元でxを平行移動してもよい。よって、平行移動 した結果xはBの元のtA係数一次結合であるとしてよい。x= 0ならばそれ でよい。そうでないとする。係数が0でないB の元のうち、ノルムの最大な ものを考える。係数がtAに入るのだから、それはxよりノルムが大きい。B からそれを抜いてxを加えても、一次独立なままでノルムは短くなっている。
よって最小性に反する。
格子の生成元が与えられたとき、その最小基底はLenstra[5]のアルゴリズム によって求まる。このときかかる計算時間は行列の掃き出しよりもずっと短い。
参考文献
[1] R. Couture, P. L’Ecuyer, and S. Tezuka, On the distribution of k-dimensional vectors for simple and combined Tausworthe sequences, Math. Comp. 60 (1993), 749–761.
[2] Luc Deveroye, Nonuniform random variate generation. Springer-Verlag, 1986.
[3] 伏見正則,乱数, 東京大学出版会, 1989.
[4] Knuth, D. E. The Art of Computer Programming. Vol. 2. Seminumerical Algorithms 3rd Ed. Addison-Wesley, 1997.
[5] Lenstra, A. K. Factoring multivariate polynomials over finite fields. J.
Comput. System Sci. 30, 235-248.
[6] F.J. MacWilliams and N.J.A. Sloane, The theory of error correcting code.
North-Holland, 1977.