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?

  • 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