# Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

The complexity of computing discrete logarithms in a multiplicative group modulo a prime $$p$$ is assumed to be sub-exponential time. The complexity is determined by $$q$$, the biggest factor of the group order $$p-1$$. Is there any group $$\mathbb{Z}_p^*$$ such that discrete logarithms are easier than subexponential in $$q$$?

• maybe this post can help you. crypto.stackexchange.com/questions/54345/… – OneUser May 25 '20 at 23:31
• @OneUser but this discusses only weaknesses in form of small subgroups. I wondered if there is any field in which the dlog is easier than sub-exponential in the largest subgroup order. – LinusK May 26 '20 at 11:26

As far as I am aware, all the recent progress on discrete log algorithms which derived pseudopolynomial efficiencies took place for the case of small characteristic fields $$GF(p^n)$$ with a structured exponent $$n$$. So the best complexity is still exponential in $$\log N$$ where $$N$$ is the size of the subgroup under consideration. So nothing better than generic DL complexity seems to be known.
Even there, the online phase complexity seems to be $$\geq (\log N)^{1/3}.$$ See this paper for a discussion. Here is a quote:
In practice, however, an adversary may have access to the description of the group $$G$$ long before it has to solve a discrete-log problem instance. In particular, the vast majority of real-world cryptosystems use one of a handful of groups, such as NIST P-256, Curve25519, or the DSA groups.
• Would it be surprising if there was a polynomial time algorithm solving dlogs in very small subgroups of finite fields e.g. $C_{7}$ or $C_{11}$ ? – LinusK Sep 17 '20 at 17:18