I need to find out $\log_g {-1}$ in $\mathbb{Z}_n$ where $n$ is an odd prime and $g$ is a primitive root mod $n$. How do I do that?
Discrete logarithm to a primitive root base
1
$\begingroup$
number-theory
discrete-logarithms
-
2Do you know what log_g 1 is? – 2010-12-20
-
0It's $\varphi(n) = n - 1$. – 2010-12-20
-
1Correct. Now what would be special about -1? – 2010-12-20
-
0@KarlX: It's not very common to use $n$ to denote a prime: it is usually used to denote a composite number, with $p$ (or in some situations, $\ell$) used for primes (and $q$ for prime powers). – 2010-12-20
-
0I don't know what's special about -1..? – 2010-12-20
-
2Try squaring $-1$. – 2010-12-20
1 Answers
1
Seems you are looking for $x$ such that $g^x = -1$.
$x = \frac{n-1}{2}$ seems to work because $\phi(n)=n-1$ and g is primitive root and $g^{\phi(n)}=1$