5
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ For your bonus question, note that $$\log_g(a)\equiv\log_g(-a)+\frac{p-1}{2}\pmod{p-1}.$$ So you're asking if we can determine whether $\log_g(a)$ is in the interval $[1,\frac{p-1}{2}]$ or in the interval $[\frac{p+1}{2},p-1]$. It seems as if answering that question for $g^ka$ for various $k$ could be used to compute $\log_g(a)$, but since I haven't worked out the details, I'm just posting this as a comment. $\endgroup$
    – Joe Silverman
    Commented Jan 9, 2023 at 18:52
  • $\begingroup$ @JoeSilverman yes that is correct. If solving discrete log is hard, can we at least easily determine which interval $\log_g a$ is in? $\endgroup$
    – Craig Feinstein
    Commented Jan 9, 2023 at 22:15
  • $\begingroup$ Look up the Blum-Micali algorithm. $\endgroup$
    – Craig Feinstein
    Commented Jan 26, 2023 at 0:41

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. I just added a bonus question. $\endgroup$
    – Craig Feinstein
    Commented Jan 9, 2023 at 15:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .