Blum-Blum-Shub
Blum-Blum-Shub(B.B.S.)は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。
漸化式は次のような形をしている。
xn+1 = (xn) mod M
ここで M=pq は2つの素数 p と q の積である。アルゴリズムの各ステップにおいて、xn から何らかの出力が得られる。この出力は一般に xn のビットパリティを使うか、または xn の1ビット以上の最下位ビット列を使う。
2つの素数 p と q は共に、(mod 4 で)3 と合同で(このとき、それぞれの平方剰余数の4つの平方根のうち、平方剰余であるものがちょうど一つである)、かつ gcd(φ(p-1), φ(q-1)) が小さいのが望ましい(これにより、反復周期が長くなる)。
Blum-Blum-Shub の興味深い性質として、任意の xi の値を次のように直接計算することができる。
x i = ( x 0 2 i mod ( p − 1 ) ( q − 1 ) ) mod M {\displaystyle x_{i}=\left(x_{0}^{2^{i}{\bmod {(}}p-1)(q-1)}\right){\bmod {M}}}