# Inverting exponentiation modulo a prime

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.

• 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. – Anurag A Oct 16 at 17:51
• 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? – Joshua Frank Oct 16 at 17:56
• it's actually $i\not\equiv j\bmod {p-1}$ – Roddy MacPhee Oct 17 at 11:07