5
$\begingroup$

I recently found this problem which asks you to find an algorithm to find all $X$ such that $X^A \equiv B \pmod{2K + 1}$.

Is there something special about the modulus being odd that allows us to solve it?

  • 1
    Exhaustive search will solve $x^a\equiv b\pmod c$ whether $c$ is even or odd, so you can always solve it (at least, in theory).2012-01-19
  • 0
    Dear @Gerry: By "you can always solve it", I guess you mean: "you can always decide if it is soluble, and solve it if it is". Don't you?2012-01-19
  • 0
    @Pierre, yes, that would have been a better way to say it.2012-01-19
  • 0
    The range is quite large $(2K \leq 10^9)$. Exhaustive search can't solve $1000$ cases in $2$s I think. Does this problem have anything to do with _primitive roots_ or _discrete logarithm_?2012-02-25

1 Answers 1

2

The author of the problem once wrote an article about baby-step-giant-step algorithm (but in Chinese).

The baby-step giant-step is a meet-in-the-middle algorithm computing the discrete logarithm.

I think this article may help you.

http://en.wikipedia.org/wiki/Baby-step_giant-step