Both methods, of course, will work.
However, from an efficiency standpoint, (1) is considerably better. Here's why:
- The general strategy of both methods is to pick random numbers $R$, check to see that they have no small prime factors (smaller than a value $Q$), and then apply a rather expensive primality test (such as Miller-Rabin) to them.
- The probability of a random number $R$ that we have already tested to have no prime factors smaller than $Q<R$ is about $log(Q)/log(R)$, and hence the number of expensive primality tests we expect to need is about $log(R)/log(Q)$.
Now, with method 2, after we pick a number $R_1$ at random, you will check to make sure it has no small factors smaller than some $Q$. If it didn't, you'll run the expensive primality test on it, and if it wasn't prime, you'll go and pick another random number $R_2$ and try again, checking if that small number had no small factors. The key point is that the effort you put into checking whether number $R_1$ had factors smaller than $Q$ cannot be reused when checking number $R_2$. Therefore, we cannot make $Q$ that large (as we'll start spending a large amount of time just testing small factors).
On the other hand, with method 1, we set up a sieve that lists which numbers within the range have no factors smaller than some value $Q$, and then test those numbers that have no such factors. Here, we pick the first number $R_1$ within the sieve, and run the expensive primality test on it, and if it wasn't prime, we'll go to the second number with no small factors in the sieve. Here's the point: almost all the time taken in checking for small factors was taken setting up the sieve; once we've done that, going to the next number is essentially free. That is, this method gets to reuse the effort in checking our test numbers for small factors.
Because of this, we can make the value $Q$ in method 1 considerably larger before it starts to become counterproductive; and because of this larger $Q$ value, fewer of the expensive tests are needed.
Now, as for security; method (2) has the obvious advantage that each prime of the correct size will be chosen with exactly equal probability, while with method (1), primes that sit over a long sequence of composites will be chosen with somewhat greater probability. On the other hand, while (1) does choose primes with unequal probability, there's no know way that a factorization method can take advantage of that. Because of this, method (1) is considered safe.
