1
$\begingroup$

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?

  • 2
    Do you know what log_g 1 is?2010-12-20
  • 0
    It's $\varphi(n) = n - 1$.2010-12-20
  • 1
    Correct. 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
  • 0
    I don't know what's special about -1..?2010-12-20
  • 2
    Try squaring $-1$.2010-12-20

1 Answers 1

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$