2024.05 Vol.1

It’s All Coming Together

The multiplication operation over a finite field (modulo prime) has a quirky property used in cryptography…buckle up for a fun abstract algebra recap.

x^2 ≡ q (mod p)

q is a quadratic residue modulo p.

A number in a finite field is described as quadratic residue if it has a square root in the field. So in the above example, there exists a x which when squared is q. But what is up with that weird residue name? Well, we are used to numbers having two square roots in the field of real numbers, for example, √9 = 3 and -3. It turns out, numbers in a finite field also have two roots, but they depend on congruence instead of negative numbers. So they get the special name quadratic residue.

Negative numbers don’t exist in a finite field. The number line is a cyclic “clock” instead of a line shooting off into infinity in both directions. So the concept of “two less than 0” is actually the order of the field minus 2. For example in a field modulo p, -x (mod p) is (p - x) (mod p). And while it is not a “negative number” like we are used to, it is still the additive inverse for the addition operation on the field. As in, x + (p - x) = 0 (mod p).

2 + (-2) = 0 (mod 7)
2 + 5    = 0 (mod 7)
7        = 0 (mod 7)
0        = 0 (mod 7)  

Additive inverse example in the finite field modulo 7.

The square operation doesn’t use addition though, x^2 = x * x, it uses the multiplication operation of the field. So what exactly does it mean to multiply an additive inverse with itself? This is the crux of why there are two square roots for a value, and it is very easy to visualize in the field of real numbers where the negative value gets “canceled out” e.g. (-3) * (-3) = 9. But why does this property still exist in a finite field?

The addition and multiplication operations are not independent, but are connected by the distributive property requirement: a * (b + c) = a * b + a * c. Using this and the required identity properties (1 * x = x and 0 + x = x) we can see how additive inverses work with multiplication.

0
0 * x
(1 + (-1)) * x
1 * x + (-1) * x
x + (-1) * x

(-1) * x is the additive inverse of x.

So multiplying by -1 flips something to its additive inverse. What if you have some non-one numbers?

(-y) * (-x)
((-1) * y) * ((-1) * x)
(-1) * (-1) * y * x
1 * y * x
y * x

-y * -x = y * x, additive inverses cancel out even in multiplication-land!

A finite field’s addition and multiplication operation’s meet the above requirements so these properties hold. The relevant take-away here is that a quadratic residue (a.k.a. the square) has two roots, x (mod p) and its additive inverse (p - x) (mod p). And given that the order p is always a prime number, so an odd number, one root will be even and one root will be odd. Think about it, if x is odd its inverse is even and vice versa. Remember that! (Personally, I’ll forget this in about six months and need to re-read this post.)