1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Thank you! As a followup confirmation, despite x=1 being a solution, the order of the subgroup using 1 as a generator should still be 1, right? Since 1 would be a solution for x^n = 1 mod p for any n $\endgroup$
    – Ymi
    Nov 15, 2023 at 6:31
  • $\begingroup$ Yes, $1$ is of order 1 and $-1$ is of order 2. $\endgroup$ Nov 15, 2023 at 6:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.