# Is there a quick method of listing certain elements of a cyclic group?

I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc.

"List all Elements $$x$$, where $$x^2 = 2$$ in $$\mathbb{Z}_{31}$$

Okay, so the naive approach would be to iterate the group, multiply the element with itself and check if its residue modulo $$31$$ would be $$2$$.

So we are searching for every element which has a quadratic residue of $$2$$ in $$\mathbb{Z}_{31}$$.

Is there any "pen and paper" solution to do this, without having to iterate every element? Is there a theorem which could be used here?

Since this is a field, you know that the polynomial $$x^2-2=0$$ may have up to 2 roots, no more. You could use the quadratic formula (since the polynomial ring over a field is an integral domain) but this would require the extraction of a square root. But it is certainly more efficient than checking all elements.
Also if if $$a$$ in $$x^2-a$$ is a square then you can factor $$(x^2-a)=(x-b)(x+b)$$ where $$b^2=a.$$
• A polynomial over a field has coefficients from the field and arithmetic is in the field. So in this case you have that $x^2-2$ is equivalent to $x^2+29$ since $-2\equiv 29 \pmod{31}.$ – kodlu Feb 5 '20 at 20:55