Blum Blum Shub
||This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. (September 2013)|
|This article relies on references to primary sources. (September 2013)|
Blum Blum Shub takes the form:
where M=pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1.
The seed x0 should be an integer that is co-prime to M (i.e. p and q are not factors of x0) and not 1 or 0.
The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue) and gcd(φ(p-1), φ(q-1)) should be small (this makes the cycle length large).
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's Theorem):
where is the Carmichael function. (Here we have ).
The generator is very slow. However, there is a proof reducing its security[clarification needed] to the computational difficulty of the computing modular square roots, a problem whose difficulty is equivalent to factoring. When the primes are chosen appropriately, and O(log log M) lower-order bits of each xn are output, then in the limit as M grows large, distinguishing the output bits from random should be at least as difficult as factoring M.
Let , and (where is the seed.) We can expect to get a large cycle length for those small numbers, because . The generator starts to evaluate by using and creates the sequence , , , = 9, 81, 82, 36, 42, 92. The following table shows the output (in bits) for the different bit selection methods used to determine the output.
|Even parity bit||Odd parity bit||Least significant bit|
|0 1 1 0 1 0||1 0 0 1 0 1||1 1 0 0 0 0|
- Blum, Lenore; Blum, Manuel; Shub, Mike (1 May 1986). "A Simple Unpredictable Pseudo-Random Number Generator". SIAM Journal on Computing 15 (2): 364–383. doi:10.1137/0215025.
- Blum, Lenore; Blum, Manuel; Shub, Mike (1982). Comparison of Two Pseudo-Random Number Generators. Advances in Cryptology: Proceedings of CRYPTO '82. Plenum. pp. 61––78.
- Geisler, Martin; Krøigård, Mikkel; Danielsen, Andreas (December 2004). About Random Bits. available as PDF and Gzipped Postscript