\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 $i=1,\ldots,p-1$.
So, $1\equiv(\prod_{i<p}(xi))/(p-1)!\equiv x^{p-1} (\bmod p)$.

 This test rejects typical composite $p$. Other composite $p$ can be actually
factored by the following tests:

\paragraph {Square Root Test.}\ 

{\bf Lemma:} For each y and prime p, the equation $(x^2\bmod p) = y$ has at
most one pair of solutions $\pm x$.

{\bf Proof:} Let $x,x'$ be two solutions: $y\equiv x^2 \equiv {x'}^2\pmod p$.
Then $x^2-{x'}^2 = (x-x')*(x+x')\equiv0\pmod p$. We have a product of two
integers which is congruent to $0$, i.e.\ divisible by $p$. Therefore $p$ must
divide at least one of the factors. (Otherwise $p$ is composite, and $\gcd(p,
x+x')$ {\em actually gives} us its factor). So, either $x - x' \equiv 0\pmod p$
or $x+x'\equiv 0\pmod p$ i.e.\ $x \equiv\pm x' \pmod p$. {\bf End of proof.}

In particular $x^2 \equiv 1\pmod p$ implies $x \equiv \pm 1$. Note that this
does NOT hold if $p$ is composite, since its factors can be spread between
$(x-x')$ and $(x+x')$. Then $y$ could have more than one $\pm$ pair of roots.

\paragraph{Rabin-Miller Test.} Let us combine these tests into $T(x,p)$ which
uses given $x$ to prove $p$ is composite. Let $p\!-\!1 = q*2^k$, with odd $q$.
$T$ sets $x_0 = (x^q\bmod p)$, $x_i=(x_{i\!-\!1}^2\bmod p)= (x^{q*2^i}\bmod
p)$, $i\le k$. If $x_0= 1$, or one of $x_i$ is $-1$, $T$ gives up. If $x_k
\neq1$, Fermat Test rejects $p$. Otherwise there is $z= x_i\neq\pm 1$, such
that $(z^2\bmod p) = x_{i+1} = 1$. Then the Square Root Test factors $p$.

First, for each odd composite $p$, we show that $T$ succeeds with {\em some}
$x$, mutually prime with $p$. If $p=a^j, j>1$, 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\neq1 \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<k$ then $(x_i)^2 \equiv 1 \pmod p$.
Take $x'= 1 + b*(1/b\bmod a)*(x\!-\!1)$. Check: $x'\equiv1\equiv x'_i \pmod b$,
while $x'_i \equiv x_i\pmod a$. Thus, either $x_i$ or $x'_i$ is not $\pm 1$.

Now, $T(y,p)$ succeeds on step $i$ with {\em most} $y$: function $y\mapsto x*y$
is 1-1 and $T$ cannot fail with both $y$ and $x*y$. This test can be repeated
for many randomly chosen $x$. Each time $T$ fails, we are twice more sure that
$p$ is prime. The probability that $T$ fails $300$ times on a composite $p$ is
$< 2^{-300} <1/N$, where $N$ is the number of particles in the known Universe.

% Primes \in P: http://www.cse.iitk.ac.in/news/primality.html