How do I generate HUGE random prime numbers?

I need to implement public key cryptography for a digital signature for a custom program that I'm writing, and at the moment I'm trying to implement RSA in C++ (though I'm open to other algorithms as long as they're good), but I'm not having trouble with the algorithm itself. Rather, I'm trying to figure out a good way to randomly choose from a wide range of prime numbers (but I must be CERTAIN that they're prime, otherwise using them could irrevocably corrupt the data!).

As I said, I can try other algorithms if that turns out to be necessary, and I don't know whether they even require prime numbers or not, so that may solve my problem, but elliptic curves are out because I can't trust the NSA. Also, I'm not sure how well RSA holds up against quantum computers. If a sufficiently large key will protect it even at a lower time order for cryptanalysis then it wouldn't be a problem I guess. This isn’t going to be used for anything top-secret, and in fact it’ll only be for authentication, but still, I really don’t want anyone counterfeiting the signatures.

In any case, I read that to be secure I need at least 2048 bit keys! That's a pretty huge key, especially for a product of just 2 prime numbers! My problem is that I'm having trouble finding prime numbers that big. I know how to find them, but as far as I can tell, I need to divide larger numbers by smaller numbers that I've already verified are prime, to see whether the larger numbers are prime as well (it's no use dividing by composite numbers, since they're all divisible by prime numbers, anyway). But that means that I'd have to find ALL of the prime numbers from 2 up to the incredibly huge ones that I would intend to use! I can find the first million primes in about a minute, but I’ll need numbers way bigger than that. It also means that I'd have to have enough RAM to store all of the numbers while doing so! So you can see my dilemma.

Anyway, I remember seeing some formula a long time ago for finding numbers that are guaranteed to be prime (something like perfect squares – 1 or something, but I don’t remember the exact formula, so if someone could print it for me or tell me the name so that I could look it up, I’d appreciate that). This would be fine, except for one problem: it only finds a small subset of all prime numbers and skips the rest, which wouldn’t break the algorithm, of course, but it would make it less secure, because if there are fewer numbers from which I might randomly pick, then a hacker only needs to divide the products by that reduced list to find the primes!

So to be safe, I think I should pick from all possible prime numbers within a range. I suppose alternatively I could just pick from a subset, but increase the range to compensate, so that there would still be approximately the same total quantity of prime numbers from which to choose within that larger range, but it’s already 2048 bits, so I suspect that I’d have to increase it to like 1000000000 bits or something! I don’t know what to think of this. What does everyone else think?

And I’m not using Python, so making numbers that huge in C++ is kind of a pain, but I suppose it may not be avoidable. I guess I’ll have to chain an array of long longs together in an object and then make all of the operators for them, adding the extra from overflow onto the next number in the array (or I guess I’ll have to use longs and then convert to long longs before doing the operation so that I’ll even be able to keep the overflow). And I do a square root at one point, so that I can divide only by potential factors less than that, and implementing a square root on a bit number centipede like that would be a HUGE pain!

I’m thinking that I’ll start the range at an already high number for minimum, so that someone doesn’t end up with numbers like 2 and 3 for a product of 6, just as a horrible fluke, but as for the uniformity of the distribution, I’m not sure whether that really matters, because even if it were distributed linearly over integers, regardless of how dense the primes are, that would just make the larger ones more likely than the smaller ones, but to compensate for that, it’ll be harder to factor their products, because they could theoretically have a larger range, I guess.

So I’m at a bit of a loss. Does anyone have any ideas? I suppose I could even use something that’s already implemented as long as it’s open source so that I can wedge it into my code.