Quadratic residues in finite field

Question

For an integer $a$ and a finite field $F_{q}$ of odd order, what is the efficient algorithm to determine $a$ is Quadratic residue or not?

Answer 1

The nonzero $a\in \Bbb F_q$ ($q$ odd) is a square iff $a^{(q-1)/2}=1$.

Answer 2

Let $q=p^n$, $p$ odd, $n\geq 1$.

As already stated, $a\in\mathbb{F}_q^\times$ is a square if and only if $a^{(q-1)/2}=1$.

Remember the Frobenius automorphism and the definition of the norm $N(a)$ for field extensions? This leads to $$\begin{align} \frac{q-1}{2} &= \frac{p-1}{2}(1+p+p^2+\cdots+p^{n-1}) \\\therefore\quad a^{(q-1)/2} &= \Bigl(\underbrace{ a^1 a^p a^{p^2} \cdots a^{p^{n-1}} }_{N(a)\in\mathbb{F}_p}\Bigr)^{(p-1)/2} \end{align}$$ Accordingly, $a$ is a square if and only if $N(a)$ is a square in the base field $\mathbb{F}_p$, therefore if and only if $$\left(\frac{N(a)}{p}\right)_2=+1$$ and there are efficient Jacobi symbol algorithms for that, e.g. the binary algorithm by Shallit and Sorenson (1993).

It remains to compute $N(a)$.

• If $a$ itself is in the base field $\mathbb{F}_p$ (maybe that is what you meant when you spoke of integer $a$), then $N(a) = a^n$ and $$\left(\frac{N(a)}{p}\right)_2 = \left(\frac{a^n}{p}\right)_2 = \left(\frac{a}{p}\right)_2^n = \left(\frac{a}{p}\right)_2^{n\bmod{2}}$$ Consequently:
  • If $n$ is even, then every $a\in\mathbb{F}_p^\times$ is a square of some element in $\mathbb{F}_q^\times$.
  • If $n$ is odd, then $a\in\mathbb{F}_p^\times$ is a square in $\mathbb{F}_q^\times$ if and only if it is a square in $\mathbb{F}_p^\times$, that is, if and only if $\bigl(\frac{a}{p}\bigr)_2=+1$.

• If $a$ is not restricted to the base field, then computing $N(a)$ is probably easiest with a normal basis which takes the form $$\left(\beta, \beta^p, \beta^{p^2}, \ldots, \beta^{p^{n-1}}\right)$$ with a suitable $\beta\in\mathbb{F}_q^\times$. The nice thing about such a basis is that taking $p$-th powers amounts to nothing more than a cyclic shift of the coefficient vector. Thus, obtaining the Frobenius conjugates of $a$ is very cheap, and you just need to multiply those $n$ conjugates together to obtain $N(a)$.

  With other bases, you can still resort to a square-and-multiply scheme, as suggested by Robert Israel. But then computing $N(a)$ has roughly the same computational cost as computing $a^{(q-1)/2}$: Both take $\operatorname{O}(\log q)$ field multiplications. There is probably no point in going via $N(a)$ then.

Answer 3

It depends on how you have your finite field elements represented. Finite fields have cyclic multiplicative groups, which means you have a generator $\alpha$ and then every (nonzero) element can be represented as a power of $\alpha$. Often there is a built-in table of the elements represented as these powers, if the exponent is even then the element is a quadratic residue.