**Rabin's One-way Function.** Pick random prime numbers **p,q,|p|=|q|** with 2
last bits **=1**, i.e. with odd . Then is called a
Blum number. Its length should make factoring infeasible.

Let be the set of *quadratic residues*, i.e. numbers of the form
.

**Lemma.** If **n=pq** is a Blum number then is a
permutation of .

**Proof:** Let and . Let . It
is odd, so is an integer. Since **2t** is a multiple of both
**p-1** and **q-1**, according to the Little Fermat Theorem divides both **p** and **q** (and, thus **n**). Then . Q.E.D.

**Lemma.** Inverting **F** on random **x** is equivalent to factoring **n**.

**Proof.** Let for a fraction of . Then
, while for a fraction of **x**.
The Square Root Test would factor **n** given any such which
could be found in about 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)!/(n! ^{2})** is
divisible by every prime

Note that fast VLSI circuits exist to multiply large numbers and check primality.

A perfect way to encrypt a message **m** is to add it bit by bit to
a random string **S** of the same length **k**. The resulting encryption 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.
*Public Key* Cryptosystems use two keys. One key is needed
to encrypt the messages and may be completely disclosed to the public. The *
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 ; . Here a Blum number **n=pq** is chosen by the Decryptor and is public, but
**p,q** are kept secret. The Encryptor chooses at random and sends
. Assuming factoring is intractable for the adversary,
**S** should be indistinguishable from random strings (even when 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 . So,
he can find , 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 . Anyone can verify **x**, but nobody can
forge it since only the legitimate user knows factors of **n** and can take
square roots.

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
*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.

Wed Aug 21 20:35:42 EDT 1996