Inverse of integer power in modulo ring

Question

For a prime $n$ and a generator $g$ of the multiplicative Group $\mathbb Z/n\mathbb Z$, $b = g^a \mod n$ is a bijection for $a \in \{0,\dotsc,n-2\}$ and $b \in \{1,\dotsc,n-1\}$. But how can I calculate its inverse?

Concrete example in Mathematica:

n = 13;  PrimeQ[n];
g = PrimitiveRoot[n];
a = Range[0, n - 2]
b = PowerMod[g, a, n]

Results in

a == {0, 1, 2, 3, 4, 5,  6,  7, 8, 9, 10, 11}
b == {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10,  7}

Basically I want a from b directly, currently I'm stuck using a lookup table for the inverse, which seems wrong.

(I'm trying to implement Rader's FFT algorithm which uses this)

score 3 · Accepted Answer · answered Mar 22 '13 at 23:21

3

Essentially, you are asking about how to solve the discrete logarithm problem. It seems that there aren't any fast ways of doing it (e.g. none in polynomial time). The Wikipedia article I linked has a list of currently used algorithms.

answered Mar 22 '13 at 23:21

Daniel Miller

2,262

Ah great, didn't even come across that on my search. – pascal Mar 22 '13 at 23:33

Inverse of integer power in modulo ring

1 Answers1