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 p in [n,2n] but by no prime power
pi > 2n. So, (log((2n)!/(n!2))) /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.
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.