The Quadratic Generator

Let $n=pq$, where $p,q$ are primes ${}\equiv{3}\hbox{ (mod }{4})$. For each prime, $a$ is a square if and only if $-a$ is not a square (Lemma 22). This implies that, if ${x}\equiv{\pm a_1}\hbox{ (mod }{p})$ and ${x}\equiv{\pm a_2}\hbox{ (mod }{q})$, there will be exactly one choice which makes $x$ a square mod $n$. Hence, if $b$ is a square mod $n$, exactly one of its four square roots will also be a square. This principal square root will be denoted by $\sqrt b$.

The quadratic generator uses a randomly chosen square $x$ (called the seed) not divisible by $p$ or $q$ to generate a sequence of 0's and 1's (bits). The sequence is $a_i$ mod 2, where $a_0=x$ and ${a_{i+1}}\equiv{\sqrt{a_i}}\hbox{ (mod }{n})$:

$$x \hbox{mod }2\quad\sqrt x\hbox{ mod }2 \quad\sqrt{\sqrt{x}}\hbox{ mod }2\quad\dots$$

(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 $n=589=19(31)$ and $x=81$, the sequence of $a_i$ is

$$81\quad9\quad586\quad175\quad112\quad443\quad214\quad237\dots$$

(note that $\sqrt 9=-3$, not 3) which gives the sequence of bits 11010101.