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:
// 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$?