# Understanding Quadratic Residue Modulo n Structure

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

• 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." – hardmath Oct 11 '15 at 8:38

• 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. – hardmath Oct 11 '15 at 15:36