# Checking if discrete logarithm is $\geq\frac{\varphi(p)}2$ in polynomial time?

Given $p$ a prime, $g$ generator of $\Bbb Z_p^*$, and $h\in\Bbb Z_p^*$, that uniquely defines some $z\in[0,\varphi(p)[$ such that $g^z\equiv h\pmod p$.

Is it possible to determine in polynomial time if $\displaystyle z\geq\frac{\varphi(p)}2$ ?

• Reason for negative vote? – Brout Feb 22 '18 at 5:17
• Given such an oracle it shouldn't be hard to find the discrete logarithm in polynomial time. Just multiply $h$ with $g^{[\frac{p}{4}]}$ (Gauss brackets to round down to integer) if the answer was no, or with $g^{[\frac{3p}{4}]}$ if yes, to get the second highest bit.... – j.p. Feb 22 '18 at 6:59
• @j.p.: do you want to make that an answer? That's the obvious reply; that $z \ge \phi(p)/2$ is a hard bit, and so deriving it is no easier than doing the full discrete log. – poncho Feb 22 '18 at 8:04
• @Turbo: The initial question gave no upper bound for $z$, and thus formally has a trivial answer. Perhaps that motivated whoever downvoted. – fgrieu Feb 22 '18 at 12:03

Given an oracle that tells you for any $h\in\mathbb{Z}_{p-1}^\times$ if the discrete logarithm $\log_g(h)$ is $\ge\frac{p}2$ or not, allows you to find $x := \log_g(h_0)$ for fixed $h_0$ with about $\log_2 p$ queries:
The query $\log_g(h_0)\stackrel{?}\ge\frac {p-1}2$ gives you one bit of information $z_0 := \lfloor\frac{2x}{p-1}\rfloor\in\{0, 1\}$, and you know that $h_1 := h_0\cdot g^{-z_0\cdot\frac{p-1}2}$ has a discrete logarithm $\log_g(h_1) \in \{0, 1, \dots, \frac{p-3}2\}$.
So if you multiply $h_1$ with $g^{\lfloor\frac{p-1}4\rfloor}$ you get an element $h_1'$ with discrete logarithm $\log_g(h_1')\in\{\lfloor\frac{p-1}4\rfloor, \dots, \lfloor\frac{3p-7}4\rfloor\}$, and querying $\log_g(h_1')\stackrel{?}\ge\frac {p-1}2$ gives you (roughly) another bit of information by cutting the interval in half.
You can repeat this step of multiplying an adaptively chosen power of $g$ to query the oracle, halving the intervals in every step until you find a single value from which then you can calculate the discrete logarithm $x$.