Generating Diffie-hellman parameters (generator)

Question

I'm trying to implement a diffie-hellman key exchange. 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, isPrime, genRandomPrime, genRandomBits, and a few more) are available.

Would it work to look for a safe prime q, so that every number n for which gcd(n,q) == 1 should be a generator, right?

Answer 1

You've already gotten the ritual admonishment not to roll your own crypto if you care at all about your security, so here's how to find a generator mod a safe prime q. A number g in the closed range [2, q - 2] is a generator if and only if g^((q-1)/2) != 1 mod q, which you should compute with the standard algorithm for modular exponentiation. Choose random values of g until one passes the test.