Understanding Blum Blum Shub algorithm. (Python implementation)

Question

Please help me to understand BBS algorithm. I did this implementation:

class EmptySequenseError(Exception):                                  
    pass                                                              


class BlumBlumShub(object):                                           
    def __init__(self, length):                                       
        self.length = length                                          
        self.primes = e(1000)  # Primes obtained by my own Sieve of Eratosthenes implementation.                                                                            

    def get_primes(self):                                             
        out_primes = []                                               
        while len(out_primes) < 2:                                    
            curr_prime = self.primes.pop()          
            if curr_prime % 4 == 3:                                   
                out_primes.append(curr_prime)                         
        return out_primes                                             

    def set_random_sequence(self):                                    
        p, q = self.get_primes()                                      
        m = p * q                                                     
        self.random_sequence = [((x+1)**2)%m for x in range(self.length)]

    def get_random_sequence(self):                                    
        if self.random_sequence:                                      
           return self.random_sequence                               
        raise EmptySequenseError("Set random sequence before get it!")

And I have several questions. At first I do not want to use random library, it is too naive. My sequence is increasing, it is not absolutely random. How to prevent increasing in returned sequence? And I do not understand this part of the algorithm description:

At each step of the algorithm, some output is derived from x_n+1; the output is commonly either the bit parity of x_n+1 or one or more of the least significant bits of x_n+1.

Please explain to me what does it mean?

Edit summary:

• The algorithm is corrected.
• Quote substituted to en.wikipedia quote.

Answer 1

    for x in range(self.length):                                  
        self.random_sequence.append((x ** 2) % m) 

Just generates [(x ** 2) % m for x in range(self.length)], which is roughly x_n+1 = n² mod M.

The algorithm is supposed to be: x_n+1 = x_n² mod M

Do you see where your version is different?

---

As for the quote - you don't say where it's from, but Wikipedia has:

At each step of the algorithm, some output is derived from x_n+1; the output is commonly either the bit parity of x_n+1 or one or more of the least significant bits of x_n+1.

It means that x_n+1 is the seed for the next iteration, but not the pseudo-random number returned. Instead, the return value is derived from x_n+1 by counting its bit parity (this yields either 0 or 1 each iteration), or by taking only some number of top bits.