Next: The Next Bit Theorem Up: Pseudo-random number generators Previous: Pseudo-random number generators   Contents

Let , where are primes . For each prime, is a square if and only if is not a square (Lemma 22). This implies that, if and , there will be exactly one choice which makes a square mod . Hence, if is a square mod , exactly one of its four square roots will also be a square. This principal square root will be denoted by .

The quadratic generator uses a randomly chosen square (called the seed) not divisible by or to generate a sequence of 0's and 1's (bits). The sequence is  mod 2, where and :

(from a practical point of view, it is simpler to generate the sequence starting with the last number and squaring)

As a small example with and , the sequence of is

(note that , not 3) which gives the sequence of bits 11010101.

Translated from LaTeX by Scott Sutherland
2002-12-14