Understanding Diffie-Hellman - Choosing a bad g I am taking a class on Cryptology, and I'm having a hard time understanding the potential pitfalls of Diffie-Hellman. Specifically, the professor gave the following problem:


  Alice and Bob want to use Diffie-Hellman for key agreement and choose
  p = 982734982635928741927391824619283719654192837198273923771,
  however, they do not know how to calculate a relative prime, and hire
  Evan (Eve in disguise) to generate one for them. Evan gives them g =
  584451952932889263219289637911613296416146180021897568955. 
  
  Explain what Evan did, and how this makes it easy for him to find the
  secret key that Alice and Bob agreed to, and find that secret key.


I understand that the value of choosing a g that has a large sub group of possible keys (i.e. you wouldn't want to choose g = 1, because then all keys would be = 1, no matter the other numbers) but I'm not understanding how that would impact this case with such a large g. Could anybody explain how I'd go about this question?
There are two tricks that Evan could have played in selecting the $g$:


She could have selected a $g$ that has a small order; that is, $g^x$ could take on a small number of possible values.
She could have selected a $g$ that has a large but smooth order; that is, $g^x$ could take on a number of possible values, but that total number is a product of small primes.


Here's why Evan could take advantage of this second point: if the order $g$ has a prime factor $r$, then given $g^x$, it's possible to determine $x \bmod r$ in $O(\sqrt{r})$ time.  Hence, if the order of $g$ consists only of small factors, then Eve can compute $x \bmod r$ for all the small prime factors, and from that, reconstruct $x$.

In either case, the question is: what's the order of the value $g$ that Evan picked?  Well, one important thing that helps us determine that value; the order is always a factor of $p-1$.  So, the very first step is factoring $p-1$.  Then, you can go through all the prime factors of $p-1$, and use this fact: if $r$ is a factor of $p-1$, the order of $g$ is a multiple of $r$ if $g^{(p-1)/r} \ne 1$.  That should let you determine the order of $g$ without a huge amount of pain.