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