Previous: Lucas Numbers Algorithm, Up: Other Algorithms [Index]
urandomb関数は，乱数生成器から出てくる鎖状のビット列を用いて乱数を生成しています。
この生成器が良いいランダム性を保持している限り，生成される乱数もうまくばらけたN bitの
値になっているはずです。
urandomm関数は，0<=R<Nの範囲の乱数を生成します。方法としては，
R<Nを満足するようになるまで，ceil(log2(N)) bitのRを抽出します。
大概，１，２回計算すれば出てきますが，生成器がおかしくなって1bit程度しか出力しなくなったりすると，繰り返し
計算する必要が出てきます。
Mersenne Twister乱数生成器は，松本 & 西村(see References)が提唱したものです。 これは繰り返しのない2^19937-1周期の生成器です。2^19937-1がMersenne素数なのでこの名がついています。乱数状態保存変数は624ワード(32bit /word)長で，32bit wordごとにXORとシフトを用いて与えられますので非常に高速です。ランダム性に優れており，GMPではデフォルトのアルゴリズムになっています。
線型合同乱数生成器は，色々なテキストに解説があり，例えばKnuth本 volume 2 (see References)があります。 法をM，パラメータをAとCで与え，状態保存はSに行い，ここにS <- A*S+C mod Mの計算を繰り返して生成を行います。各ステップでは新しい状態が，Mを法として前の状態の線型関数として計算されるので，この名前がついています。
GMPでは，2^Nのみ法としてサポートしており，現在の実装では特に最適化も行っていません。 Nが小さい時にはオーバーヘッドも大きくなり，Nが大きいと各ステップにおける乗算が重くなっていきます。あらゆる点でMersenne Twister乱数生成器が優れているので，通常のアプリケーションに利用することはお勧めしません。
どちらの乱数生成器でも，現在の乱数生成状態は出力値をじっくり観察して，いくつかの線型計算(Mersenne Twisterの場合は体 GF(2)上）を試してみると予測できてしまう恐れがあります。一般的には，長いハッシュ値などを利用せずに暗号化を行うようなアプリケーションに，乱数生成器の生の出力を使うことは望ましいことではありません。