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