Blum Blum Shub


Blum Blum Shub is a pseudorandom number generator proposed in 1986 by Lenore Blum, Manuel Blum and Michael Shub that is derived from Michael O. Rabin's one-way function.
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 and not 1 or 0.
The two primes, p and q, should both be congruent to 3 , and should be safe primes with a small gcd/2, .
An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi'' value directly :
where is the Carmichael function..

Security

There is a proof reducing its security to the computational difficulty of factoring. When the primes are chosen appropriately, and O 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 solving the Quadratic residuosity problem modulo M.

Example

Let, and . 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, 236, 36, 31, 202. The following table shows the output for the different bit selection methods used to determine the output.
The following Common Lisp implementation provides a simple demonstration of the generator, in particular regarding the three bit selection methods. It is important to note that the requirements imposed upon the parameters p, q and s are not checked.

"Counts and returns the number of 1-valued bits in the BITS."


when )

)

)
)
"Returns a function of no arguments which represents a simple
Blum-Blum-Shub pseudorandom number generator, configured to use the
generator parameters P, Q, and S, and returning three values:
the even parity bit of the number,
the least significant bit of the number,
the number x.
---
Please note that the parameters P, Q, and S are not checked in
accordance to the conditions described in the article."
) ;; x0 = seed

#'
;; x = x^2 mod M
)

;; Compute the random bit based on x.

;; Update the state such that x becomes the new x.

)))))
;; Print the exemplary outputs.






)))