# Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $$q$$ that divides $$p-1$$ and $$q$$ is to specify a subgroup with the order $$q$$. But why do we do that? Why do not we work on the group with the order $$p$$ and need a subgroup with order $$q$$.

This is for security reasons (discrete logarithm calculation algorithms) or for computational optimization?

• Commented Oct 5, 2020 at 22:42

The group you're working with does not have order $$p$$. In discrete log schemes, you're not working in a finite field, $$F_p$$, but rather a multiplicative group $$1,...,p-1$$, which has order $$p-1$$. Since $$p$$ is a prime, $$p-1$$ is composite (as long as $$p > 3$$). Group theory tells us that there is a subgroup of size $$d$$ for every $$d$$ that divides $$p-1$$.$$^{1}$$ By choosing a subgroup of order $$q$$, where $$q$$ is prime, we ensure that there are no (non-trivial) subgroups. This avoids small subgroup confinement attacks.

As mentioned in the other answer and comments, there are easy ways to find suitable $$p$$ and $$q$$. One is by using primes, $$p$$ and $$q$$, such that $$p = 2q + 1$$. Such a $$p$$ is called a safe prime. Another is by setting $$p = qr + 1$$, where $$r$$ has (potentially) unknown factorization. The group generated by this $$q$$ is called a Schnorr group.

$$^1$$ This claim is not true in general. It is true for the group of a finite field. See this Wikipedia section Existence of subgroups of a given order for the gory details in the general case. This math.stackexchange answer is a nice proof for the group of a finite field.

One relevant point is that if $$p-1$$ is not of a form like $$2q$$ for $$q$$ prime, then it could be difficult to find the multiplicative order of an element. You can't use Lagrange's theorem to determine the order if you can't factor $$(p-1)/2$$, but the mere fact that you haven't yet found a small factor wouldn't show that one doesn't exist. Using a $$p$$ where $$p-1$$ has a large known prime factor could be the difference between knowing the order of an element and merely hoping that the order is large.

• There are alternatives to safe primes; we can have $p = qr + 1$, for a value of $r > 2$. With a prime of this form, it is easy to find an element of order $q$ (even if you don't know the factorization of $r$). One advantage is that it is easier to find primes of this form (select $q$ to be a prime of moderate size, say, 256 bits, then search for a prime of the form $qr + 1$) than it is to find a safe prime. Personally, I prefer safe primes; however we should realize that it's not the only alternative Commented Oct 6, 2020 at 11:42
• @poncho Good point. In fact, that was part of my motivation for the way that I worded the final sentence (about $p-1$ having a large known prime factor rather than just saying that it was of the form $2q$). Note that if $p-1 = qr$ then you do in fact have a factorization of $p-1$ even if it isn't a complete factorization. In that scenario you might be able to determine the order of some elements (including all of those with order $q$) but not others. I agree that safe primes are preferable. Commented Oct 6, 2020 at 11:52
• What poncho is said the Schnorr group Commented Oct 6, 2020 at 17:32