Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
For DH key agreement, one must begin with a generator of a cyclic group g.
However, intuitively to me at least, it seems that g may be expensive to calculate for a random cyclic group mod some large prime p.
How is this done efficiently on the fly for Diffie Hellman?
Probably this is naive, however it would seem one must check each element of the group to test it's generative properties...
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.
