DLOG ⊆ NP

Inclusion · folklore

Statement

The decision version of DLOG — given $(\mathbb{G},g,h,t)$, decide whether some $x\le t$ satisfies $g^x=h$ — is in NP: the exponent $x$ is a polynomial-size certificate, checked with one exponentiation — folklore.

Notes

• Membership in $\mathbf{NP}\cap \mathbf{coNP}$ additionally needs the group order and its factorization, certified by Pratt primality certificates, so that the discrete logarithm is unique and certifiable — folklore; the $\mathbf{coNP}$ side is DLOG ⊆ coNP.