\newpage\section {Randomness in Computing.\label{rand}}
\subsection {A Monte-Carlo Primality Tester.\label{prime}}
The factoring problem seems very hard. But to test a number for having factors
turns out to be much easier than to find them. It also helps if we supply the
computer with a coin-flipping device. We now consider a Monte Carlo algorithm,
i.e.\ one that with high probability rejects any composite number, but never a
prime. See: [Rabin 1980], [Miller 1976], [Solovay, Strassen 1977].
\paragraph{Residue Arithmetic.} $p|x$ means $p$ is a divisor of $x$. $y=
(x\ \bmod p)$ denotes the residue of $x$ when divided by $p$, i.e.\ $y\in[0,p
\!-\!1]$, $p|(x\!-\!y)$. $x \equiv y\pmod p$ means $p|(x\!-\!y)$. Residues can
be added, multiplied and subtracted with the result put back in the range $[0,p
\!-\!1]$ (by adding an appropriate multiple of $p$). E.g., $-x$ means $p\!-\!x$
for residues $\bmod\ p$. We use $\pm x$ to mean either $x$ or $-x$. If $r$ and
$p$ have no common divisors $>1$ (are mutually prime), division $(x/r \bmod p)$
is possible, since $x\to(r*x\bmod p)$ is one-to-one on $[0,p\!-\!1]$.
Operations $+,-,*,/$ obey all usual arithmetical laws. $\gcd(x,y)$ is the
greatest (and divisible by any other) common divisor of $x$ and $y$. It can be
found by Euclid's Algorithm: $\gcd(x,0)=x$; $\gcd(x,y)=\gcd(y,(x\bmod y))$, for
$y>0$. By induction, $g=\gcd(x,y)=A*x-B*y$, where integers $A=(g/x\bmod y)$ and
$B= (g/y\bmod x)$ are produced as a byproduct of Euclid's Algorithm.
We will need to compute $(x^q\bmod p)$ in polynomial time. We
cannot multiply $x$ $q$ times, since it takes $q>2^{\|q\|}$ steps.
Instead we compute all numbers $x_i=(x_{i\!-\!1}^2\bmod p)=
(x^{2^i}\bmod p),i<\|q\|$. Then we represent $q$ in binary, i.e.\
as a sum of powers of $2$ and multiply $\bmod\ p$ the needed
$x_i$'s.
\paragraph{Fermat Test.} The Little Fermat Theorem for every
$x\in[1,p\!-\!1]$ and prime $p$ says: $x^{(p\!-\!1)} \equiv 1 \pmod p$.\\
Indeed, the sequence $(xi\bmod p)$ is a permutation of $1,\ldots,p{-}1$.
So, $1{\equiv}(\prod_{i1$, then $x= (1+p/a)$
is good for $T: (1+p/a)^{p\!-\!1}= 1+(p/a)(p\!-\!1)+
(p/a)^2*(p\!-\!1)(p\!-\!2)/2+\ldots \equiv 1\!-\!p/a\not\equiv1 \pmod
p$, since $(p/a)^2 \equiv 0 \pmod p$. So the Fermat Test works.
Otherwise $p=a*b$, $\gcd(a,b)=1$. Take the {\bf greatest} $i\leq k$ such
that $x_i\neq 1$ for some $x$ mutually prime with $p$. Such $i$ exists,
since $(-1)^q \equiv -1$ for odd $q$. If $i