\newpage\subsection{Cryptography.\label{crypt}}
{\bf Rabin's One-way Function.} Pick random prime numbers $p,q,\|p\|=\|q\|$ with 2
last bits $=1$, i.e.\ with odd $(p{-}1)(q{-}1)/4$. Then $n=p \ast q$ is called a
Blum number. Its length should make factoring infeasible.
Let $Q(n)$ be the set of {\em quadratic residues}, i.e.\ numbers of the form
$(x^2\bmod n)$.
{\bf Lemma.} If $n=pq$ is a Blum number then $F: x\mapsto (x^2\bmod n)$ is a
permutation of $Q(n)$.
{\bf Proof:} Let $x=F(z)\in Q(n)$ and $y=F(x)$. Let $t=(p{-}1)(q{-}1)/4$. It
is odd, so $u=u(n)=(t{+}1)/2$ is an integer. Since $2t$ is a multiple of both
$p{-}1$ and $q{-}1$, according to the Little Fermat Theorem $x^t-1\equiv
z^{2t}-1$ divides both $p$ and $q$ (and, thus $n$). Then $y^u\equiv
x^{2u}=xx^t\equiv x\ (\bmod n)$. Q.E.D.
{\bf Lemma.} Inverting $F$ on random $x$ is equivalent to factoring $n$.
{\bf Proof.} Let $F(A(y))=y$ for a fraction $\varepsilon$ of $y\in Q(n)$. Then
$F(A(y))=y=F(x)$, while $A(y)\ne\pm x$ for a fraction $\varepsilon/2$ of $x$.
The Square Root Test would factor $n$ given any such $x,A(F(x))$ which
could be found in about $2/\varepsilon$ random trials. Conversely, knowing a
secret (factors of $n$) makes inverting $F$ easy; such one-way permutations,
called ``trap-door,'' have many applications, such as cryptography (see below).
Picking a prime number is easy since primes have density $1/O(\|p\|)$. Indeed,
one can see that ${2n\choose n}$ is divisible by every prime $p\in[n,2n]$ but
by no prime $p\in[\frac23n,n]$ or prime power $p^i>2n$. So, $(\log{2n\choose
n})/\log n = 2n/\log n -O(1)$ is an upper bound on the number of primes in
$[n,2n]$ and a lower bound on that in $[1,2n]$. Note that fast VLSI circuits
exist to multiply large numbers and check primality.
\paragraph {Public Key Encryption.}
A perfect way to encrypt a message $m$ is to add it $\bmod\,2$ bit by bit to a
random string $S$ of the same length $k$. The resulting encryption $m \oplus S$
has the same uniform probability distribution, no matter what $m$ is. So it is
useless for the adversary who wants to learn something about $m$, without
knowing $S$. A disadvantage is that the communicating parties must share a
secret $S$ as large as all messages to be exchanged combined. {\em Public Key}
Cryptosystems use two keys. One key is needed to encrypt the messages and may
be completely disclosed to the public. The {\em decryption} key must still be
kept secret, but need not be sent to the encrypting party. The same keys may be
used repeatedly for many messages.
Such cryptosystem can be obtained [Blum, Goldwasser 1982] by replacing the
above random $S$ by pseudorandom $S_i= (s_i\cdot x)$; $s_{i+1} =(s_i^2\ \bmod
n)$. Here a Blum number $n=pq$ is chosen by the Decryptor and is public, but
$p,q$ are kept secret. The Encryptor chooses $x,s_0$ at random and sends
$x,s_k, m\!\oplus\! S$. Assuming factoring is intractable for the adversary,
$S$ should be indistinguishable from random strings (even when $s_k$ is known).
Then this scheme is as secure as if $S$ were random. The Decryptor knows $p,q$
and can compute $u,t$ (see above) and $v=(u^{k-1}\bmod t)$. So, he can find
$s_1=(s_k^v\bmod n)$, and then $S$ and $m$.
Another use of the intractability of factoring is digital signatures [Rivest,
Shamir, Adleman 1978], [Rabin, 1979]. Strings $x$ can be released as
authorizations of $y = (x^2\bmod n)$. Anyone can verify $x$, but nobody can
forge it since only the legitimate user knows factors of $n$ and can take
square roots.
\vfill\subsubsection* {Go On!}
You noticed that most of our burning questions are still open. Take them on!
Start with reading recent results (FOCS/STOC is a good source). See where you
can improve them. Start writing, first notes just for your friends, then the
real papers. Here is a little writing advice:
A well written paper has clear components: skeleton, muscles, etc.
The skeleton is an acyclic digraph of basic definitions and statements,
with cross-references. The meat consists of proofs (muscles) each
{\em separately} verifiable by competent graduate students having to
read no other parts but statements and definitions cited.
Intuitive comments, examples and other comfort items are fat and skin: a
lack or excess will not make the paper pretty. Proper scholarly references
constitute clothing, no paper should ever appear in public without!
The trains of thought which led to the discovery are blood and guts: keep
them hidden. Other vital parts, like open problems, I skip out of modesty.
\vfill\paragraph {Writing Contributions.} {\small Section~\ref{models} was
prepared by Elena Temin, Yong Gao and Imre Kifor (BU), others by Berkeley
students: \ref{compress} by Mark Sullivan,
\ref{games}.0 by Eric Herrmann, \ref{win} by Elena Eliashberg,
\ref{halt-gm} by Wayne Fenton and Peter Van Roy,
\ref{gm-reduce} by Carl Ludewig, \ref{gm-reduce} by Sean Flynn,
\ref{gm-reduce} by Francois Dumas, \ref{invert} by Jeff Makaiwi,
\ref{search}.1 by Brian Jones and Carl Ludewig,
\ref{compl} by David Leech and Peter Van Roy,
\ref{tile} by Johnny and Siu-Ling Chan, \ref{average} by Deborah Kordon,
\ref{kolm} by Carl Ludewig, \ref{pseudor}
by Sean Flynn, Francois Dumas, Eric Herrmann, \ref{crypt} by Brian Jones.}