Demonstrating Diffie-Hellman key exchange using only p, A, B; I'm trying to figure out how to demonstrate DH key exchange using what is given to me. I'm unsure of how to tackle the problem. 



Question:

Demonstrate Diffie-Hellman key exchange.

Given p=104933, A=324, B=5832. Prime factors for p-1 {2,37,709}

A and B are Alice and Bob secret keys respectively.

What is the value of the shared key?



Process to solve:

So there are 5 steps to DH key exchange.


Alice and Bob share prime p and generator g
Alice sends g^a mod p to Bob
Bob sends g^b mod p to Alice
Alice computes the shared key
Bob computes the shared key


I get stuck at step 1 though because I'm unsure of how I'm supposed to find the generator given this information.
I guess the problem is to find the generator $g$.

Denote the factors for $p-1$ to be $p_1 =2, p_2 =2,p_3 = 37, p_4 = 709$.

With $p$, and the factorization of $\phi(p)$ you can find a generator in the following way:

Randomly choose an element $x$ from $Z_p$ and test whether $x^{\phi(p)/p_i}$ mod $p \ne 1$ for every $i =1,2,3,4$. If this is the case, $x$ is a generator. Otherwise, just select another element to run the test. You should find one soon. (Please refer to wikipedia for the method.)

Since $5^{2\times 37 \times 709}$ mod 104933 = 104932, $5^{2\times 2 \times 709}$ mod 104933 = 45751, $5^{2\times 2 \times 37}$ mod 104933 = 92770. Then 5 is a generator.

Next steps are basic algebra, I will stop here.