Next: The Next Bit Theorem
Up: Pseudo-random number generators
Previous: Pseudo-random number generators
Let , where are primes
. For each prime, is a square if and only if is not
a square (Lemma 22).
This implies that, if
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
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
(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
that , not 3) which gives the sequence of bits 11010101.
Translated from LaTeX by Scott Sutherland