5
$\begingroup$

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$ ?

$\endgroup$
  • $\begingroup$ Reason for negative vote? $\endgroup$ – Brout Feb 22 '18 at 5:17
  • 5
    $\begingroup$ 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.... $\endgroup$ – j.p. Feb 22 '18 at 6:59
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho Feb 22 '18 at 8:04
  • $\begingroup$ @Turbo: The initial question gave no upper bound for $z$, and thus formally has a trivial answer. Perhaps that motivated whoever downvoted. $\endgroup$ – fgrieu Feb 22 '18 at 12:03
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.