# Diffie-Hellman: *assumed* largest prime factor of order of $g$?

that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?

The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$, then compute $g=a^{(p-1)/q}\pmod{p}$ for some random $a$. So the order of $g$ is $q$ if $g\neq 1$.

• – mikeazo Dec 19 '15 at 3:53
• Basically, smooth integers are rare (this is one reason why factoring is so hard, since sieve-type factoring algorithms require a lot of smooth numbers), so if $p$ is randomly chosen, it is highly unlikely that $p-1$ will be smooth. – fkraiem Dec 19 '15 at 4:31

I've read in several places that somehow the largest prime factor $q$ of $|g|$ (order of $g$) is assumed to be large enough without actually knowing $q$. How do they do that?
Actually, both references talk about the behavior of the TLS client when negotiating a DHE-based ciphersuite. The server proposes $p$ and $g$ as a part of the exchange, and hence the client doesn't know $q$. This doesn't mean that $q$ is unknown, only that the client must trust that the server generated the group properly (which isn't totally unreasonable, as the client needs to trust the server to do other things properly as well). Now, it would have been reasonable for the server to include the value $q$ as well (so a paranoid client could check it); they didn't include that in the protocol.
The only method I'm aware of is to start with a large enough prime $q$ and search for prime $p=nq+1$...
That is certainly one method which is used in practice. An alternative method would be to search for a Sophie-Germaine prime, that is, two values $p$ and $q = (p-1)/2$ which are prime simultaneously; in this case, any quadratic residue (other than 1, of course) would work as a generator. This takes a bit of more work than the method you listed; however if you're generating a group once, this is irrelevant.