Generating Diffie-Hellman parameters I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a generator g?

Restricted by the multiprecision library that I have to use, only a few basic operations (+, *, -, /, pow, modExp, modMult, mod, gcd, isProbablyPrime, genRandomBits, and a few more) are available.

I read that in a cyclic finite group $Z_q$ where $q$ is a safe prime, every element is a generator of that group. So I assume I should start by generating a safe prime $q$ first:

Pseudocode:

 // find a safe prime q
 WHILE NOT isProbablyPrime(q)
     WHILE NOT isProbablyPrime(p)
        p = genRandomBits(1024)               
     q = 2*p+1


But how do I now find a generator for $Z_q$?
Just stick to the standard algorithm, also remember that you are working in $\mathbb{Z}_p^*$.

Select $q$ with at least $2k$ bits, that means you are targeting $k$ bits security. In the RFC at least 160 bits is recommended for $q$. In addition select a prime $p$ with at least 1024-bit.

Regarding the generator, we know that every generator will generate the subgroup of order $2q$ or $q$. The reason that $g=2$ is chosen is that is desirable for faster computations of modular exponentiation.

You will find all the information regarded to Diffie-Hellman implementation in RFC. Also there's a method for generating $p$,$q$ and alternatively $g$, if desired.