$a^n \equiv r \pmod p$
given $r, a, p$
$p$ is an odd prime
$p \equiv 3 \pmod 4$
Here, $a$ is a primitive root modulo $p$, so the first equation has a unique solution $0 \le n . It is easy to tell whether $n$ is even by Euler's criterion. Is it possible to decide whether $n\equiv 0 \pmod 4$, without explicitly solving for $n$?
?
– 2012-06-21