1
$\begingroup$

$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$?

  • 1
    Actually, it is impossible to determine if $n \equiv 0 \pmod 4$, even after solving to find $n$. If $n$ is a solution, then so is $n+p-1$. Do you mean to restrict $n?2012-06-21
  • 0
    Yes, only for $n2012-06-21
  • 1
    It may be my limitation, but I'm a bit pessimistic here. The reason is that, unlike in the case when you want to determine whether $2\mid n$, the answer depends on the choice of $a$. For example replacing $a$ with its inverse modulo $p$ will replace $n$ with $(p-1)-n$ and a problem analogous to the one described by Erick Wong. Of course, if we had $p\equiv 1\pmod 4$, then we would simply check whether $r^{(p-1)/4}\equiv 1\pmod p$ or not.2012-06-21
  • 1
    Given a QR $r$, for half of the primitive roots the answer is yes, for the other half it is no. But I have no ideas about how to tell which half (for $r$) the primitive root $a$ belongs to. There may be a connection with quadratic residues mod $p^2$.2012-06-21

1 Answers 1