blum blum shub generator algorithm example

( let (( even-parity-bit ( get-even-parity-bit x )) ( least-significant-bit ( get-least-significant-bit x ))) ( declare ( type bit even-parity-bit )) ( declare ( type bit least-significant-bit )) Update the state such that x becomes the new x. Please note that the parameters P, Q, and S are not checked in accordance to the conditions described in the article.' ( declare ( type ( integer 0 * ) p q s )) ( let (( M ( * p q )) M = p * q ( x s )) x0 = seed ( declare ( type ( integer 0 * ) M x )) #' ( lambda () x = x^2 mod M ( let (( x ( mod ( * x x ) M ))) ( declare ( type ( integer 0 * ) x )) Compute the random bit(s) based on x. ( defun get-number-of-1-bits ( bits ) 'Returns the number of 1-valued bits in the integer-encoded BITS.' ( declare ( type ( integer 0 * ) bits )) ( the ( integer 0 * ) ( logcount bits ))) ( defun get-even-parity-bit ( bits ) 'Returns the even parity bit of the integer-encoded BITS.' ( declare ( type ( integer 0 * ) bits )) ( the bit ( mod ( get-number-of-1-bits bits ) 2 ))) ( defun get-least-significant-bit ( bits ) 'Returns the least significant bit of the integer-encoded BITS.' ( declare ( type ( integer 0 * ) bits )) ( the bit ( ldb ( byte 1 0 ) bits ))) ( defun make-blum-blum-shub ( &key ( p 11 ) ( q 23 ) ( s 3 )) '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 (seed), and returning three values: (1) the number x, (2) the even parity bit of the number, (3) the least significant bit of the number. It is important to note that the requirements imposed upon the parameters p, q and s (seed) are not checked. The following Common Lisp implementation provides a simple demonstration of the generator, in particular regarding the three bit selection methods. The following table shows the output (in bits) for the different bit selection methods used to determine the output.

Blum blum shub generator algorithm example