# Why is it that in DSA, the order of the subgroup, $q$, is chosen such that it divides $p - 1$?

Consider the DSA key generation:

1. A large prime $p$ is chosen;
2. A smaller modulus $q$ is chosen such that $p - 1$ is a multiple of $q$;
3. A generator $g$ s.t. $\operatorname{ord}_p(g) = q$ is chosen.

My question is -- why do we require that $p - 1$ be a multiple of $q$? Is there any underlying mathematics I'm missing? Thanks.

• Lagrange's theorem. – SEJPM Dec 12 '15 at 22:19
• That is, if $q$ isn't a divisor of $p-1$, then there won't be a subgroup of size $q$ – poncho Dec 12 '15 at 22:20
• Thanks guys. I almost thought of it myself. Feel free to write an answer so that I can accept it. – d125q Dec 12 '15 at 22:21
• It's actually done the other direction: find prime q of the desired size (e.g. 256 bits) then find prime p = kq+1 of the desired size (e.g. 2048 bits). 'find' can either be 'choose a random candidate and test (Miller-Rabin plus optional Lucas)' or 'construct from half-size primes, recursively (Shawe-Taylor) and tweak'. See A.1 C.3 C.6 of FIPS186, on the NIST CSRC website on days the President isn't having a temper tantrum. – dave_thompson_085 Jan 17 at 5:50

As was noted in the comments the reason for $q$ having to divide $p-1$ is Lagrange's theorem:
Lagrange's theorem [...], states that for any finite group $G$, the order (number of elements) of every subgroup $H$ of $G$ divides the order of $G$.
In the case of DSA we are working in subgroups of $\mathbb F_p$ (which has order $p-1$). By Lagrange's theorem every subgroup has to have an order $q$ such that $q$ divides $p-1$.