DLOG ⊆ coNP

Inclusion · folklore

Statement

The decision version of DLOG, which given $(\mathbb{G},g,p,X,t)$ asks whether the $x\in [p]$ with $g^x=X$ satisfies $x\le t$, is in coNP — folklore.

Sketch

A no-instance is certified by $x$ itself: $g^x=X$ and $x>t$ are checkable in polynomial time, and $x$ is unique once the order $p$ of $g$ is certified by its prime factorization with primality certificates.