\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