Generating REALLY big primes

Take a look at how TrueCrypt does it. Also, take a look at Rabin-Miller for testing large pseudoprimes.

You don't generate prime numbers exactly. You generate a large odd number randomly, then test if that number is prime, if not generate another one randomly. There are some laws of prime numbers that basically state that your odds of "hitting" a prime via random tries is (2/ln n)

For example, if you want a 512-bit random prime number, you will find one in 2/(512*ln(2)) So roughly 1 out of every 177 of the numbers you try will be prime.

There are multiple ways to test if a number is prime, one good one is the "Miller-Rabin test" as stated in another answer to this question.

Also, OpenSSL has a nice utility to test for primes:

$ openssl prime 119054759245460753
1A6F7AC39A53511 is not prime