# On public keys compression, why an even or odd y coordinate corresponds to the positive / negative sign respectively?

This is a paragraph from Andreas' book on compressed/uncompressed public keys.

Chapter 4 - Section - Key Formats

Whereas uncompressed public keys have a prefix of 04 ,compressed public keys start with either a 02 or a 03 prefix. Let’s look at why there are two possible prefixes: because the left side of the equation is y^2 , that means the solution for y is a square root, which can have a positive or negative value. Visually, this means that the resulting y coordinate can be above the x-axis or below the x-axis. As you can see from the graph of the elliptic curve in Figure 4-2, the curve is symmetric, meaning it is reflected like a mirror by the x-axis. So, while we can omit the y coordinate we have to store the sign of y (positive or negative), or in other words, we have to remember if it was above or below the x-axis because each of those options represents a different point and a different public key. When calculating the elliptic curve in binary arithmetic on the finite field of prime order p, the y coordinate is either even or odd, which corresponds to the positive/negative sign as explained earlier. Therefore, to distinguish between the two possible values of y, we store a compressed public key with the prefix 02 if the y is even, and 03 if it is odd, allowing the software to correctly deduce the y coordinate from the x coordinate and uncompress the public key to the full coordinates of the point. Public key compression is illustrated in Figure 4-7

What I don't get is that bold text.

Why an even or odd y coordinate corresponds to the positive / negative sign?

For example, are all even public keys below the x-axis?

There is no such thing as a negative or a positive value when you're talking in a finite field.

For example, in `Z7`, the field of integers modulo `7`. There holds:

• `0` = `7` = `14` = `-7`
• `1` = `8` = `15` = `-6`
• `2` = `9` = `16` = `-5`
• ...

So you can't say that the number `2` is positive, because it's equal to `-5`.

Despite that, the square root still has two solutions. For example, `3^2` = `9` = `2`, `4^2` = `16` = `2`. Thus both `3` and `4` are square roots of `2`.

So we need a way to say which solution we want. Turns out, that when reduced to a range of 0-6, the two solutions of the square, one is odd and the other is even.

• +1 for clarifying that pos & neg are not meaningful in modulo fields – Richard Dec 7 '15 at 1:38
• @Pieter Wuille, i am getting confused with the powers of 2s. I tried the exercise with `y² mod p = (x³ + 7) mod p , for p = 5, x = 3`, i get 2 solutions as you explained, and it happens that you can find the odd/even solution (`2² mod 5 = 3² mod 5`) for `y²`. I had to force this to come up with `2` and `3` as square roots of `4` although it makes sense as the `real` roots are`2` and `-2`, and `-2 mod 5 = 3`. What if `x=4`? We get `1² mod 5` and ... `2.44948974² mod 5`. A fractional number can't be odd or even. – Souza Feb 15 '18 at 13:39
• Square root here does not refer to the classical real square root. It refers to the inverse function of `x^2 mod p`. So we say `y` is the square root of `x mod p` iff `y^2 mod p = x`. – Pieter Wuille Feb 15 '18 at 16:05
• @PieterWuille i got it now!!! Thank you. Sorry for my misconception. Lastly, why does one need to know if s*2>N at: `is_high_s = s*2 > N` and `v = 27 + ((y % 2) ^ (1 if is_high_s else 0))` ? – Souza Feb 20 '18 at 18:56
• Because every number that has a square root has in fact two (negating a number does not change its square). Thus we need a way to convey which of the two square roots is the one meant. – Pieter Wuille Feb 20 '18 at 19:35

Elliptic curves are of the form y^2 = f(x).

This means there are two roots to the equation. i.e. if we know an x there are two possible y values that satisfy the equation (y & -y). Because we are using a modulo type number field, it happens that the even and odd translate to y and -y