# How do Quadratic Residues work and how do they relate to Diffie Hellman?

Can someone explain Quadratic residues to me in english? I keep reading forums with all the math symbols and it's hard to follow. And how are they incorporated in Diffie-Hellman? Is there a difference in using them vs cubic residues?

Can someone explain Quadratic residues to me in english?

A value $$x$$ is a Quadratic residue modulo $$p$$ if there exists a value $$t$$ for which $$t^2 \bmod p = x$$.

That is, we take $$t$$, square it (that's the Quadratic part), and then take it modulo $$p$$ (that's the residue part, that is, the part that's left over after removing all the multiples of $$p$$), and that gives us the value $$x$$. If such a process can give us $$x$$, we say that $$x$$ is a Quadratic Residue.

For example, $$2$$ is Quadratic Residue modulo $$7$$ (because if we start with $$3$$, square it, and then take that result modulo $$7$$, we end up with $$2$$); however $$3$$ is not (can be verified by computing $$1^2 \bmod 7, 2^2 \bmod 7, 3^2 \bmod 7, …, 6^2 \bmod 7$$)

Also, in this answer, I have been careful to always say "Quadratic Residue modulo $$p$$"; obviously, the same value $$x$$ can be a Quadratic Residue modulo some prime $$p$$ and not modulo another prime $$q$$. Normally, you'll see the statement "\$x" is a Quadratic Residue"; they mean modulo something, but that something is implicit (as they are working in a specific group, which should be obvious from context).

Important facts:

• If $$p$$ is a prime greater than 2, then some of the values between $$1$$ and $$p-1$$ will be Quadratic Residues modulo $$p$$, and some will not be. In fact, precisely half of those values will be and half will not.

• If $$p$$ is a prime, then $$a \times b \bmod p$$ will be a Quadratic Residue modulo $$p$$ if either both $$a$$ and $$b$$ are Quadratic Residues, or both are not.

• If $$p$$ is a prime, it turns out to be simple to check where $$x$$ is a Quadratic Residue mod $$p$$.

And how are they incorporated in Diffie-Hellman?

Mostly, it's not. If the Diffie-Hellman generator $$g$$ is not a Quadratic Residue modulo $$p$$, then given $$g^a \bmod p$$, we can determine whether $$a$$ is even or odd; given $$g^a \bmod p, g^b \bmod p$$, we can determine whether $$g^{ab} \bmod p$$ is a Quadratic Residue modulo $$p$$ or not. On the other hand, we generally perform Diffie-Hellman using a generate that generates a large prime subgroup; such a generator will always be a Quadratic Residue modulo $$p$$, and so examining the values $$g^a \bmod p, g^b \bmod p$$ doesn't tell us anything.

Is there a difference in using them vs cubic residues?

If $$p$$ is a prime where $$p \equiv 2 \bmod 3$$, then cubic residues modulo $$p$$ are uninteresting; all values $$x$$ are Cubic Residues modulo $$p$$.

If $$p$$ is a prime with $$p \equiv 1 \bmod 3$$, then a third of the values between $$1$$ and $$p-1$$ will be cubic residues modulo $$p$$, and two thirds will notbe. On the other hand, the same Diffie-Hellman logic applies; if $$g$$ generates a large prime subgroup, then $$g$$ will be a cubic residue modulo $$p$$, and so will $$g^a \bmod p, g^b \bmod p, g^{ab} \bmod p$$ as well...