# Find the minimum power in mod equation

Given 3 positive integers $x$, $z$ and $k$, find the smallest non-negative integer $y$, such that $k\;\%\;z = (x^y)\;\%\;z$ and $x$, $z$ and $k$ will be ($1 \le x, z, k \le 10^9$). We've to report otherwise if such integer doesn't exist.

$a\;\%\;b$ means remainder when $a$ is divided by $b$ and $a^b$ means $a$ raised to the power of $b$.

-
In other words, $k\equiv x^y \pmod z$ (k\equiv x^y \pmod z). This is the discrete logarithm problem. –  anon Aug 19 '11 at 18:04
@anon: % is standard notation in some programming languages. –  Billy Aug 19 '11 at 18:20
@tendua: I'm sorry, but I don't understand what the question is; are you asking for an "efficient" method for computing the discrete log, an explanation of what you are being asked to do, an idea for how to implement it? –  Arturo Magidin Aug 19 '11 at 18:31
@tendua: The wikiarticle linked to by anon tells us that the existence of a polynomial time (often equated with efficient) algorithm for computing the discrete log is an unsolved problem. Means that most likely you need to settle with one of the approaches listed there (several alternatives). If you're into quantum stuff, you can ask Peter Shor (he seems to regularly post in CSTheory.SE). –  Jyrki Lahtonen Aug 19 '11 at 19:58
@tendua: The discrete log problem is a "hard" problem; there are no known "very efficient" algorithms. The Wikipedia page has links to seven of the better known/faster algorithms, none of which is polynomial time. –  Arturo Magidin Aug 19 '11 at 19:59