Quadratic Residue Modulo n:

$a \in \mathbb Z_n^*$ is quadatic residue of modulo n if there exists an element $x \in \mathbb Z_n^*$ such that

$$x^2 \equiv a \mod n$$

I'm not getting the intuition behind this structure, How is it helpful in Number theory. Can anybody explain it to me.

  • $\begingroup$ This is a pretty broad (unfocused) question, following on your question about what "multiplicative group" modulo $n$ is. Identifying quadratic residues modulo a prime is a classic topic in number theory, with roots in the studies of Fermat, Euler, and Gauss. Please narrow the focus of your Question beyond "I'm not getting the intuition behind this structure." $\endgroup$ – hardmath Oct 11 '15 at 8:38

If you're asking why we study such a structure, one reason is that it makes an appearance in cryptography. Using Legendre and Jacobi symbols for quadratic residues you can break certain cryptographic systems. So in a way, studying that structure helped in improving the system and guarding against that kind of attacks.

  • $\begingroup$ Historically the attacks on cryptographic systems you mention were studied as methods for factoring large numbers, e.g. by Fermat by expressing an integer $N$ as a difference of two squares. Improvements in this approach led to the quadratic sieve and the general number field sieve. $\endgroup$ – hardmath Oct 11 '15 at 15:36

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.