Implementation

import functools

@functools.cache
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Blum Blum Shub is a PRNG algorithm published in 1986.

Formula

The algorithm is very short and simple. Starting from the seed, the next state can be computed by passing the current state through the following formula.

f(x) = x² mod M

In this formula, M is the product of p and q, two large primes.

The complexity in this algorithm is hidden in the parameters; the seed and the modulus M. In order to have a long cycle length and fulfill its security promises, Blum Blum Shub has a few constraints on its parameters.