1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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

$\endgroup$

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.