Cyclic groups: find power

Question

Given the group $\mathbb Z_7$ and the generator $3$, we know the values generated are

$a^0=3^0\pmod{7}=1$

$a^1=3^1\pmod{7}=3$

$a^2=3^2\pmod{7}=2$

$a^3=3^3\pmod{7}=6$

$a^4=3^4\pmod{7}=4$

$a^5=3^5\pmod{7}=5$

$a^6=3^6\pmod{7}=1$

$...$ cycle continues $...$

My question is this: Given the resulting value, the generator used, and the group, is there a way to determine the power if we assume its value is $<=5$ aside from iterating over all possible values?

In case I'm not explaining myself well, using the same generator and group from the example above, how do we find the value for $n$ in the following:

$a^n=3^n\pmod{7}=6$

My apologies if this question is stupid. It's been about 5 years since I took an Abstract Algebra course and I was thinking about this today.

Answer 1

Your example of finding $n$ in the congruence $3^n\equiv 6 \pmod{7}$ is an instance of the 'discrete logarithm' problem. This is in general a hard problem, and I think some cryptographic protocols are based on the difficulty of solving the general discrete log problem.

Here is a link with more info: http://en.wikipedia.org/wiki/Discrete_logarithm

Answer 2

In $\mathbb{Z_p}$ you would always have $a^{(p-1)}=1$ (mod $p$). This is the Fermat's little theorem..

Also, as you observed, the cycle continues, and you can find values of $n$ for which the equations hold.