Blum-Blum-Shub（B.B.S.）は、マヌエル・ブラムとLenore BlumとMichael Shubが提案した暗号論的擬似乱数生成器である。1986年に発表された (Blum et al, 1986)。漸化式は次のような形をしている。ここで "M=pq" は2つの素数 "p" と "q" の積である。アルゴリズムの各ステップにおいて、"x" から何らかの出力が得られる。この出力は一般に "x" のビットパリティを使うか、または "x" の1ビット以上の最下位ビット列を使う。2つの素数 "p" と "q" は共に、(mod 4 で）3 と合同で（これにより、それぞれの平方剰余が1つの平方根を持ち、それ自身も平方剰余となる）、かつ gcd(φ("p"-1), φ("q"-1)) が小さいのが望ましい（これにより、反復周期が長くなる）。Blum-Blum-Shub の興味深い性質として、任意の "x" の値を次のように直接計算することができる。暗号論的擬似乱数生成器であるため、情報セキュリティや暗号目的で使われる。計算量的に不利なためシミュレーションなどには向かない。セキュリティ目的での強度としては、素因数分解の複雑さを利用した暗号の品質に匹敵する。適切な素数を選べば、各 "x" の O(log log "M") ビットの下位ビット列が出力となり、"M" を無限大に近づけると、そのビット列と乱数を見分けることは、"M" を素因数分解するのと同程度かそれ以上に困難となる。素因数分解が困難であれば、十分に大きな "M" の B.B.S. の出力から、ランダムでないパターンを適切な量の計算で検出することはできない。このため、RSA暗号のような素因数分解問題を利用した暗号技術と同程度に安全とされている。gcd(φ(p-1), φ(q-1))=2を満たすような素数の組"p"、"q"であっても、短い周期を持つことがある。例えば、"p=839"、"q=5119139"の場合ではその周期は最長で129124380となるのに対し、"p=887"、"q=4842091"の場合では、"M=pq"の値がほとんど同じであるにもかかわらず、その周期は最長でも437580となる。"p=11"、"q=19"、"s=3" とする。gcd(φ("p"-1), φ("q"-1))=2 であるため、生成される擬似乱数列が反復する周期は長いことが期待できる。"x" ="s" として "x" を求めるところから始め、"x

出典:wikipedia