この疑似乱数は数学的には非常に簡単です。 2元体F2を係数とする、19937次元のベクトル空間 Vを考えます。End(V)の元で、固有多項式が既約な ものを一つとり、fとします。2^19937-1が素数で あることにより、fの周期は2^19937-1にならざるを 得ません。(fの固有値はF_2^19937を生成する体だから。)

Vのベクトルを状態とし、fを次状態関数とする力学系を 考えます。するとこの系の周期は2^19937-1。 この力学系は、0を除く全ての状態をとるわけです。

VからF_2^32の適当な線形写像gを固定し、初期ベクトルvから 力学系を動かしてgで出力をすると、 g(v), g(f(v)), g(f^2(v)), ...という32bit整数列が 得られます。

問題は、 (1)いかに実現したとき効率のよいV, f, gを探す/作るか。 (2)出力の32bit整数列が、いくつか組にしてみた場合のラティス 構造の最適化(gを選ぶ)。 の二つがあります。

(1)は、計算機のなかでのVの実現方法、fの特性多項式の既約性の 判定など、かなり計算機アルゴリズム的アイデアになります。 fの計算量がVの次元によらないような、うまいアルゴリズムがあるのです。

既約性のためには、フロベニウス写像のオーダーを計算します。 2^19937-1の素数性をうまく使って、高速に既約性を判定する アルゴリズムをつくりました。

(2)は、Lenstraらが研究した「形式ベキ級数環における数の幾何」 (最短基底)を使います。使い方は、Couture-Tezuka-Lecuyerによる ものです。

僕としては、 「純粋数学は実におどろくほど役に立っていて、人に 非難されるすじあいはない。」 という証拠を作ろうと思って研究しました。