# Why does using a prime-order subgroup in DLP improve security?

Let's consider a discrete logarithm

$$\beta \equiv \alpha ^{x} \bmod \,\, p$$

We can solve it using Pohlig-Hellman algorithm. And, if $$p-1 = tq$$ where $$q$$ is a large prime factor, we can avoid any leakages by choosing $$\beta=a^{t}$$.

This is what my professor said at lesson, however i don't succeed in understanding why it avoids any leakages. Can you explain to me why ? Also with calculations if it's possible

## 1 Answer

Probably what your professor meant is that you start with any group element $$\alpha$$, and then use $$g := \alpha^t$$ as the generator for a cryptosystem such as Schnorr signatures, as long as $$g$$ is not itself the identity.

Why? If $$g \ne 1$$, then $$g$$ is guaranteed to have prime order $$q$$, because $$g^q = (\alpha^t)^q = \alpha^{tq} = \alpha^{\phi(p)} = 1$$, and since $$q$$ is prime there are no smaller orders possible for $$g$$ (just start over with a different $$\alpha$$ if it is).

Then when you choose a public key $$\beta := g^x$$ for secret $$x$$, you're guaranteed that $$\log_\alpha \beta \equiv 0 \pmod t$$. (Of course, you could have equivalently chosen $$\beta := \alpha^{tx}$$, but precomputing $$g$$ may be cheaper.)

Now since the group generated by $$g$$ has prime order, Pohlig–Hellman has no advantage over any other DLOG algorithms.

• Can you explain me why $\log_\alpha \beta \equiv 0 \pmod t$ ? – AleWolf Nov 18 '19 at 7:51
• $\log_\alpha \beta = \log_\alpha g^x = \log_\alpha \alpha^{tx} = tx$ – Squeamish Ossifrage Nov 18 '19 at 8:09