Blum-Blum-Shub

Blum-Blum-Shub（B.B.S.）は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。

漸化式は次のような形をしている。

x_n+1 = (x_n)² mod M

ここで M=pq は2つの素数 p と q の積である。アルゴリズムの各ステップにおいて、x_n から何らかの出力が得られる。この出力は一般に x_n のビットパリティを使���か、または x_n の1ビット以上の最下位ビット列を使う。

2つの素数 p と q は共に、(mod 4 で）3 と合同で（このとき、それぞれの平方剰余数の4つの平方根のうち、平方剰余であるものがちょうど一つである）、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい（これにより、反復周期が長くなる）。

Blum-Blum-Shub の興味深い性質として、任意の x_i の値を次のように直接計算することができる。

${\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {(}}p-1)(q-1)}\right){\bmod {M}}}$