How do you make Fermat's primality test go fast? This small Lisp-function implements Fermat's primality test in a very simple way and it is very slow at $n &gt;= 10^6$ because we reach into bignum territory. 

(defun prime-p (n)
  (= 1 (mod (expt 5 (1- n)) n)))


What am I missing? I assume that this is not the form that is actually used in implementations of RSA to find appropriate primes, what is actually used?
I'm not very good at reading Lisp, so please correct me if I'm wrong, but it looks as if you're naïvely calculating $a^{n-1} \bmod n$ by first raising $a$ to the $n-1$ -th power, and then reducing the result modulo $n$.

This is a very inefficient way to implement modular exponentiation since, as you've noticed, the intermediate result $a^{n-1}$ can quickly grow to an enormous size.  It is far more efficient to reduce any intermediate results modulo $n$ while raising $a$ to the $n-1$ -th power, effectively doing the calculation directly in the ring $\mathbb Z / n \mathbb Z$ of residues modulo $n$.

Unfortunately, I don't know enough Lisp to directly suggest an efficient implementation of modular exponentiation for you, but the Wikipedia page I linked above does describe some suitable algorithms, and provides some iterative pseudocode implementations that you may be able to adapt.