1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Ah, I see, very interesting! How do I get the polynomial from a Field? $\endgroup$ – Tho Mas Feb 5 '20 at 15:36
  • $\begingroup$ 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}.$ $\endgroup$ – kodlu Feb 5 '20 at 20:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.