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

##

The Quadratic Generator

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