Suppose one is given an odd prime $p$, a generator $g$ of $(\mathbb Z/p \mathbb Z)^\*$ and two integers $a$ and $b$. Is there an efficient method to determine whether $\log\_g a < \log\_g b$? (Here we are defining $\log\_g x$ as between one and $p-1$ inclusive.)


Bonus question added later: What if we restrict the problem to $b=-a$?



Discrete log problem modified
If there were a way of doing this in time polynomial in $\log(p)$, you could solve discrete logarithm in time polynomial in $\log(p)$ by doing a binary search. That is, to find $\log\_g(a)$, first see if $\log\_g a < \log\_g (g^{(p-1)/2})$. If yes, next compare $\log\_g(a)$ to $\log\_g (g^{\lfloor (p-1)/4\rfloor})$, if no to $\log\_g(g^{\lfloor 3 (p-1)/4 \rfloor})$, etc.


