Blum-Blum-Shub（B.B.S.）は、1986年にマヌエル・ブラム、Lenore Blum、Michael Shub が発表した擬似乱数発生器である (Blum et al, 1986)。
次のような形式である。xn+1 = (xn)2modM
ここで M=pq は2つの素数p と q の積である。アルゴリズムの各ステップにおいて、xn から何らかの出力が得られる。この出力は一般に xn のビットパリティを使うか、または xn の1ビット以上の最下位ビット列を使う。
2つの素数 p と q は共に、(mod 4 で）3 と合同で（これにより、それぞれの平方剰余が1つの平方根を持ち、それ自身も平方剰余となる）、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい（これにより、反復周期が長くなる）。
Blum-Blum-Shub の興味深い性質として、任意の xi の値を次のように直接計算することができる。 x_i = \left( x_0^{2^i \bmod (p-1)(q-1)} \right) \bmod M
----------------------------------------------
出典:「フリー百科辞典ウィキペディア」(2009-01-01)
Text is available under GNU Free Documentation License.
[Blum-Blum-Shub]の改定履歴
ご利用上の注意