# DHKE: Why using safe prime gives us "safe" subgroups?

I come from the question here: Safe primes subgroup in Diffie–Hellman key exchange

Where the accepted answer states that there are only 4 possible outcomes for the order of a subgroup when using a safe prime in the Diffie-Hellman Key Exchange: (1, 2, q, p-1) where q is the Sophie Germaine prime (i.e. (p-1)/2) and p is the safe prime.

The reason for these 4 outcomes seem to be due to Lagrange's Theorem (order of subgroups must divide order of the group), but I am wondering why all values between 1 and p-1 used as the generator will produce either q or p-1 as the order. For order=1, the generator has to be the identity (1), but for order=2, why can't other values between 1 and p-1 acting as a generator produce order=2 in their subgroup? How do we see this?

An element $$x$$ has order 1 or 2 if and only if it satisfies the equation $$x^2=1$$. In a field (which $$\mathbb{Z}/p\mathbb{Z}$$ is when $$p$$ is prime), an equation of degree $$d$$ has at most $$d$$ solutions; therefore, there are at most 2 solutions to the equation $$x^2=1$$. One is $$1$$ and the other is $$-1=p-1$$. As a result, all the other non zero elements (between $$2$$ and $$p-2$$) must have order either $$p-1$$ or $$(p-1)/2$$.
• Yes, $1$ is of order 1 and $-1$ is of order 2. Commented Nov 15, 2023 at 6:49