The Quadratic Generator

Let $n=pq$, where $p,q$ are primes $\equiv3\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.