Suppose p is an odd prime, g is a primitive root of p, i < p is any integer, and $w(i) = g^i \bmod p = k$.

Note that if $i \neq j$, then $w(i) \neq w(j)$, so the map is in principle invertible.

For a given k, is there a general method for finding i? All solutions I've seen have been basically trial and error, with some clever tricks to narrow the search space if i and k happen to be certain values.

  • 1
    $\begingroup$ what you are asking is the Discrete Log Problem. There are methods to solve it but none of them are "efficient" in terms of time complexity. $\endgroup$ – Anurag A Oct 16 at 17:51
  • 1
    $\begingroup$ Ah, I didn't know that had a name. Wikipedia has a nice discussion of it here: en.wikipedia.org/wiki/Discrete_logarithm Could you make an answer of this, that I could accept? $\endgroup$ – Joshua Frank Oct 16 at 17:56
  • $\begingroup$ it's actually $i\not\equiv j\bmod {p-1}$ $\endgroup$ – Roddy MacPhee Oct 17 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.