# How to get the order of a group generator in DH?

For a DH parameter prime, if the generator $$g$$ is 2, how do I get the order $$q$$?

• This question is wrong. The group order is part of the group specification in DHKE. There’s no concept of “getting group order from the generator”. Dec 24, 2020 at 19:04

A generator $$g$$ means that $$g$$ generates the group $$\langle g \rangle =G$$. Therefore the order of the group $$ord(G)$$ is equal to the order of the generator $$ord(g)$$.

If $$2$$ ( or any other element) is not a generator that is $$\langle 2 \rangle \neq G$$ then the element $$2$$ forms a subgroup under the group operation. Then the order of $$2$$ must divide the order of the group, $$ord(2) | ord(G)$$ by the Lagrange's theorem;

if $$H$$ is a subgroup of a finite group $$G$$, then the order of $$H$$ divides the order of $$G$$

Diffie-Hellman Key Exchange can be used with multiplicative and additive groups. DHKE represents the multiplicative version and ECDH is the additive version with the Elliptic Curves over a finite field $$E(K)$$.

For the multiplicative group To find the order, factor the $$ord(G)$$ then find the smallest factor $$x$$ , $$x|ord(G)$$, such that $$g^x = 1$$, where $$g^x$$ means $$g^x = \underbrace{a \cdot a \cdot a \cdots a}_{x\text{ times}}.$$

In the additive group like ECC, you need to check that $$[x]G = \mathcal{O}$$ where $$\mathcal{O}$$ is the identity element of the curve, $$G$$ is a base element and $$[x]G$$ means $$[x]G = \underbrace{a + a + a + a}_{x\text{ times}}.$$

Both can be checked efficiently,

In the DHKE, in practice, we chose a safe prime $$p = 2 q +1$$ where $$q$$ is another prime and called Sophie Germain prime. In this case, the order of $$G$$ is only divisible by 2 and $$q$$, then we can choose the $$g$$ as the generator of the subgroup $$H$$ of order $$q$$. Since $$q$$ is a prime, then any element of $$H$$ is a generator. Take a random, or find the smallest element $$x$$, such that $$g^2 \neq 1$$ and $$g^q =1$$ then we have a generator.

In the safe prime case, we have 4 possible groups orders $$\{1,2,q,2q\}$$ and the groups are $$\{1\},\{1,-1\}$$, the quadratic residues, and the whole group. In this case, to find a generator with order $$q$$ quadratic residues is enough, and quadratic non-residues will have $$2q$$ order, other than the $$\{1,-1\}$$. To pick a generator, the law of quadratic residues can be used. The results are in Poncho's answer;

The theory behind this is the Second Supplement to Law of Quadratic Reciprocity; \begin{align}\left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8} \label{1}\tag{1} \end{align} and there is an elemtary proof of the above statement and $$\left(\frac{2}{p}\right)$$ is the multiplicative Legendry Symbol.

• $$2$$ is a square modulo $$p$$ if and only if $$p\equiv\pm 1\mod 8$$ and thus the order is $$q$$.
• $$2$$ is not a square modulo $$p$$ if and only if $$p\equiv\pm 3\mod 8$$ and thus the order is $$2q$$.

If you are looking for some examples see RFC 2412, Appendix E ‘The Well-Known Groups’).

In the case of ECDH, the process a bit more complex, We don't need to choose curves with a prime number of rational points like NIST P-224 where every element is a generator, however, it doesn't have twist security and side-channel free Montgomery ladder.

To extend kelalaka's answer, if $$p$$ is a safe prime (that is, if $$p = 2q+1$$ with $$q$$ prime), then:

• If $$p \equiv 7 \pmod 8$$, then the order of $$g=2$$ will be $$q$$

• If $$p \equiv 3 \pmod 8$$, then the order of $$g=2$$ will be $$2q$$

• If $$p = 5$$ (the only other possibility), then the order of $$g=2$$ is 4 (that is, $$2q$$)

• Nice extension, thanks, Dec 24, 2020 at 20:40