Calculating G for a give cyclic group mod P
How is this done efficiently on the fly for Diffie Hellman?


For Finite-Field Diffie-Hellman, you usually pick $p$ such that $q=(p-1)/2$ is also prime. Now Lagrange's theorem tells us that every element's order must divide the group order which is $p-1=2q$. This leaves us with four divisors: $1,2,q,2q$. Once you know that, you can simply test that your chosen candidate $g$ doesn't have order $1$ nor $2$ which you can test by checking that $g^2\neq 1\pmod p$. If you now explicitly want either of the other two orders you can test whether $g^q=1\pmod p$ and if yes you have a generator of order $q$ and if not then it has order $2q$. As to whether we can actually find the two interesting cases, Sylow's theorems guarantee this and usually you would start with $g=2$ and count up until you have a suitable candidate.