Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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
show 2 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.