I am trying to determine if $x$ is quadratic residue over a binary field ($GF(2^n)$). For finite field of type $GF(p)$ (where $p$ is prime), one can find the answer by calculating $x^{(p-1)/2}$ and checking whether it is congruent to $1$ mod $p$, but I don't know how to relate this method to the binary field. Is there any better way apart from this?

  • 3
    $\begingroup$ Every $x$ is a quadratic residue because the map $x \mapsto x^2$ is an isomorphism. $\endgroup$ Dec 22, 2015 at 7:49
  • $\begingroup$ @QiaochuYuan Great !! That is final acceptable answer for me. Could you please provide a proof or a link to it so that I can understand it better ? $\endgroup$
    – Gaurav
    Dec 22, 2015 at 11:01
  • 1
    $\begingroup$ @Gaurav Multiplicative group is cyclic with odd order $q-1$. Let $\alpha$ be a generator. Then suppose that $x = \alpha^{k}$. If $k$ is even, then $x = (\alpha^{k/2})^{2}$. If $k$ is odd then $k+(q-1)$ is even, so $x = \alpha^{k+q-1} = (\alpha^{(k+q-1)/2})^{2}$. $\endgroup$ Dec 22, 2015 at 15:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.