ssh-keygen DH Primality Testing I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh.  Reading over the man page, it says "By default, each candidate will be subjected to 100 primality tests. This may be overridden using the -a option."  I'm making an educated guess that the tests being performed are some non-deterministic test for primality (Miller–Rabin?), although the man page doesn't seem to say.  Experimenting with that -a option shows that 4 is the lowest that ssh-keygen will accept as an argument for -a.

what I'm wondering what the chances are of getting a composite number (or a non-safe prime number, or some other problematic situation) with values like 4 or 100 for -a?  Is this on the order of a 1 in 100 risk, or 1 in a million risk?

Thank you.
In ssh-keygen.c of the OpenSSH source code, there is the following call:

        if (prime_test(in, out, rounds == 0 ? 100 : rounds,
            generator_wanted, checkpoint,
            start_lineno, lines_to_process) != 0)


...and a comment for the function prime_test says:

 * perform a Miller-Rabin primality test


Therefore, it does indeed use a Miller-Rabin test. One can show that for composite $n$, at least half of the possible random choices prove the compositeness of $n$ (in fact, there are even stronger bounds), hence the confidence in $n$'s primality after $k$ runs of that test is larger than $1-2^{-k}$. In the particular case $k=100$, the probability is (larger than) roughly $1-2^{-100}=0.999999999999999999999999999999$, which is a lot.