<p>Elliptic curves are of the form y^2 = f(x).</p>

<p>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 &amp; -y). Because we are using a modulo type number field, it happens that the even and odd translate to y and -y</p>

<p><a href="https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus" rel="nofollow">https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus</a></p>

<p>This confused me too, until I figured out modulo type fields are not as normal as we expect.</p>

CC BY-SA 3.0
2016-05-15T14:54:25.003Z
Why not just transmit the y value instead as 2s complement.
Setheron
CC BY-SA 3.0
2016-05-17T00:47:39.433Z
See Pieter's answer above (very good detail). Basically a 2s complement is the modulus of the word size (in bits); so we need to use a Ns complement - where N is the modulus of the field. So a modulus of 2^n - we can use 2s complement
Richard
CC BY-SA 3.0
2015-12-05T23:19:07.033Z
2015-12-05T23:19:07.033Z
Richard
<p>There is no such thing as a negative or a positive value when you're talking in a finite field.</p>

<p>For example, in <code>Z7</code>, the field of integers modulo <code>7</code>. There holds:</p>

<ul>
<li><code>0</code> = <code>7</code> = <code>14</code> = <code>-7</code></li>
<li><code>1</code> = <code>8</code> = <code>15</code> = <code>-6</code></li>
<li><code>2</code> = <code>9</code> = <code>16</code> = <code>-5</code></li>
<li>...</li>
</ul>

<p>So you can't say that the number <code>2</code> is positive, because it's equal to <code>-5</code>.</p>

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

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

CC BY-SA 3.0
2015-12-07T01:38:35.320Z
+1 for clarifying that pos & neg are not meaningful in modulo fields
Richard
CC BY-SA 3.0
2018-02-15T13:39:33.660Z
@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
CC BY-SA 3.0
2018-02-15T16:05:23.663Z
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
CC BY-SA 3.0
2018-02-20T18:56:39.627Z
@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
CC BY-SA 3.0
2018-02-20T19:35:39.113Z
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
CC BY-SA 3.0
2015-12-06T03:01:53.407Z
2015-12-06T15:05:10.693Z
2015-12-06T15:05:10.693Z
Pieter Wuille
<p>This is a paragraph from Andreas' book on compressed/uncompressed public keys. </p>

<p><em>Chapter 4 - Section - Key Formats</em> </p>

<blockquote>
  <p>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. <strong>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.</strong>
  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</p>
</blockquote>

<p>What I don't get is that bold text. </p>

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

<p>For example, are all even public keys below the x-axis?</p>

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

(Asked by: username_0 on 2015-12-05)

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?

**Tags:** public-key


---

## 2 answers

### Answer by username_3 on 2015-12-06. Score: 14 | Accepted answer

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.

> **Comments:**
> **username_1**: +1 for clarifying that pos & neg are not meaningful in modulo fields  
> **username_4**: @username_3, 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.  
> **username_3**: 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`.  
> **username_4**: @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))` ?  
> **username_3**: 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.  

---

### Answer by username_1 on 2015-12-05. Score: 3

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

<https://en.wikipedia.org/wiki/Quadratic_residue#Prime_or_prime_power_modulus>

This confused me too, until I figured out modulo type fields are not as normal as we expect.

> **Comments:**
> **username_2**: Why not just transmit the y value instead as 2s complement.  
> **username_1**: See Pieter's answer above (very good detail). Basically a 2s complement is the modulus of the word size (in bits); so we need to use a Ns complement - where N is the modulus of the field. So a modulus of 2^n - we can use 2s complement  

---

