Generally, this problem is reduced to quadratic residue problem of modulo a big prime number. But this reduction is not applicable to Optimal Extension Fields (OEF).