(This is entirely optional. Unless you know better, it's entirely sensible to skip this and use the default settings.)
On the ‘Key’ menu, you can also optionally change the method for generating the prime numbers used in the generated key. This is used for RSA and DSA keys only. (The other key types don't require generating prime numbers at all.)
The prime-generation method does not affect compatibility: a key generated with any of these methods will still work with all the same SSH servers.
The available methods are:
The ‘probable primes’ method sounds unsafe, but it's the most commonly used prime-generation strategy. There is in theory a possibility that it might accidentally generate a number that isn't prime, but the software does enough checking to make that probability vanishingly small (less than 1 in 2^80, or 1 in 10^24). So, in practice, nobody worries about it very much.
The other methods cause PuTTYgen to use numbers that it is sure are prime, because it generates the output number together with a proof of its primality. This takes more effort, but it eliminates that theoretical risk in the probabilistic method.
There in one way in which PuTTYgen's ‘proven primes’ method is not strictly better than its ‘probable primes’ method. If you use PuTTYgen to generate an RSA key on a computer that is potentially susceptible to timing- or cache-based side-channel attacks, such as a shared computer, the ‘probable primes’ method is designed to resist such attacks, whereas the ‘proven primes’ methods are not. (This is only a concern for RSA keys; for other key types, primes are either not secret or not involved.)
You might choose to switch from probable to proven primes if you have a local security standard that demands it, or if you don't trust the probabilistic argument for the safety of the usual method.
For RSA keys, there's also an option on the ‘Key’ menu to use ‘strong’ primes as the prime factors of the public key. A ‘strong’ prime is a prime number chosen to have a particular structure that makes certain factoring algorithms more difficult to apply, so some security standards recommend their use. However, the most modern factoring algorithms are unaffected, so this option is probably not worth turning on unless you have a local standard that recommends it.