Using probabilistic compositeness tests based on Fermat's Little Theorem.
The latter says that if p is prime and 0 < x < p then x^(p-1) mod p = 1.
Given p, one chooses some x and tests the condition. If it fails p is
definitely composite.
Otherwise p might be prime but is not necessarily so since the
converse of the theorem does not hold. However if p was a randomly
chosen integer (using some non-weird distribution) and x was likewise
chosen, then p is quite likely to be prime (hence the misnomer
"probabilistic primality tests" used by many).
I checked p = 2^5000+n for n = 0,1,2... until a "probable prime"
popped up at n = 2157. That was the easy part. Then I ran the
primality prover on p. It uses some partial converses to generalised
versions of the theorem to turn "quite likely" into "definitely".
The previous record was a partition number 2^(4997 point something)
which is why I started at 2^5000.
I haven't tried Psychic Friends yet, though.
-- Rob.
PS: you DID ask!
.-. Robert.Harley@inria.fr .-.
/ \ .-. .-. / \
/ \ / \ .-. _ .-. / \ / \
/ \ / \ / \ / \ / \ / \ / \
/ \ / \ / `-' `-' \ / \ / \
\ / `-' `-' \ /
`-' Linux - 500MHz Alpha - 256MB SDRAM `-'