Editing Blum Blum Shub (section)

==Example==
Let <math>p=11</math>, <math>q=23</math> and <math>s=3</math> (where <math>s</math> is the seed). We can expect to get a large cycle length for those small numbers, because <math>{\rm gcd}((p-3)/2, (q-3)/2)=2</math>.
The generator starts to evaluate <math>x_0</math> by using <math>x_{-1}=s</math> and creates the sequence <math>x_0</math>, <math>x_1</math>, <math>x_2</math>, <math>\ldots</math> <math>x_5</math> = 9, 81, 236, 36, 31, 202. The following table shows the output (in bits) for the different bit selection methods used to determine the output.

{| class="wikitable"
|-
! [[Parity bit]]
! [[Least significant bit]]
|-
| 0 1 1 0 1 0
| 1 1 0 0 1 0
|}

The following is a [[Python (programming language)|Python]] implementation that does check for primality.

<syntaxhighlight lang="python3">
import sympy


def blum_blum_shub(p1, p2, seed, iterations):
    assert p1 % 4 == 3
    assert p2 % 4 == 3
    assert sympy.isprime(p1 // 2)
    assert sympy.isprime(p2 // 2)
    n = p1 * p2
    numbers = []
    for _ in range(iterations):
        seed = (seed**2) % n
        if seed in numbers:
            print(f"The RNG has fallen into a loop at {len(numbers)} steps")
            return numbers
        numbers.append(seed)
    return numbers


print(blum_blum_shub(11, 23, 3, 100))
</syntaxhighlight>

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'' (seed) are not checked.

<syntaxhighlight lang="lisp">
(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[n+1],
   (2) the even parity bit of the number,
   (3) the least significant bit of the number.
   ---
   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[n] s))            ;; x0 = seed
    (declare (type (integer 0 *) M x[n]))
    #'(lambda ()
        ;; x[n+1] = x[n]^2 mod M
        (let ((x[n+1] (mod (* x[n] x[n]) M)))
          (declare (type (integer 0 *) x[n+1]))
          ;; Compute the random bit(s) based on x[n+1].
          (let ((even-parity-bit       (get-even-parity-bit       x[n+1]))
                (least-significant-bit (get-least-significant-bit x[n+1])))
            (declare (type bit even-parity-bit))
            (declare (type bit least-significant-bit))
            ;; Update the state such that x[n+1] becomes the new x[n].
            (setf x[n] x[n+1])
            (values x[n+1]
                    even-parity-bit
                    least-significant-bit))))))

;; Print the exemplary outputs.
(let ((bbs (make-blum-blum-shub :p 11 :q 23 :s 3)))
  (declare (type (function () (values (integer 0 *) bit bit)) bbs))
  (format T "~&Keys: E = even parity, L = least significant")
  (format T "~2%")
  (format T "~&x[n+1] | E | L")
  (format T "~&--------------")
  (loop repeat 6 do
    (multiple-value-bind (x[n+1] even-parity-bit least-significant-bit)
        (funcall bbs)
      (declare (type (integer 0 *) x[n+1]))
      (declare (type bit           even-parity-bit))
      (declare (type bit           least-significant-bit))
      (format T "~&~6d | ~d | ~d"
                x[n+1] even-parity-bit least-significant-bit))))
</syntaxhighlight>