I read about elliptic curve cryptography $E$ over $Z_p$ where $p$ is prime number and $G$ is a base point on the curve. I noticed the points resulting from multiplication e.g. $2G$,$3G$,.....,$(N-1)G$ are always be positive numbers for $x , y$ and don't contain any negative values.

Whats the reason for these results not containing any negative values?


2 Answers 2


Actually, strictly speaking, the $x$ and $y$ values on an elliptic curve point aren't integers; instead, they are field elements. That is, the elliptic curve is defined in a field, which is a group of elements with addition and multiplication operations defined on them (along with a group of identities); the $x$ and $y$ values are members from these elements.

Now, you specify that you're doing a curve over $Z_p$; that field (often called $GF(p)$), which has precisely $p$ element, is most commonly represented by the integers between 0 and $p-1$. With this representation, we perform the addition and multiplication operations by taking the represention, adding or multiplying the two values together (using normal integer arithmetic), and then perform a modulo $p$ operation (which maps the value back into the range of 0 to $p-1$. If $p$ is prime, these operations satisfies all the required identifies of a field.

So, when you say that that points are always have positive numbers for $x, y$, what you're actually saying is that, using this standard representation, negative values never occur. That's trivially true because this representation only contains values between 0 and $p-1$, and never takes on negative values. We can easily define an alternative representation which does contain negative values; we just don't have any reason to.

  • $\begingroup$ Thanks for the answer, but what this means then in NIST P-256 (csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf): b^2c = -27 (mod p) - page 5 $\endgroup$
    – Oleg Gryb
    Commented Apr 27, 2015 at 6:10
  • $\begingroup$ ... or A = -3 mod p in tools.ietf.org/html/rfc5639 (page 6) $\endgroup$
    – Oleg Gryb
    Commented Apr 27, 2015 at 6:10
  • 2
    $\begingroup$ @OlegGryb: when talking about $Z/p$, the values $x$ and $x+p$ are considered "the same" (no matter what $x$ is). In this case, the value $A = -3$ is considered the same as $A = p-3$ (and $b^2c = -27$ is considered the same as $b^2c = p-27"). Now, $-3$ is not the standard representation of that particular field element; however it can be considered a shorthand for that element. $\endgroup$
    – poncho
    Commented Apr 27, 2015 at 7:02
  • $\begingroup$ Thanks, I've figured out it already by doing some simple math shortly after I've asked the qs :) Another confusing moment for me was mirroring a point in adding points: (x_r, y_r) -> (x_r, - y_r), but I've figured it out as well. Probably I should add another answer, because it will be definitely confusing for others. $\endgroup$
    – Oleg Gryb
    Commented Apr 27, 2015 at 16:14

While it's true that integers are just monikers for a field Fp's elements and theoretically you can call these elements whatever you want, a common way of describing elements in standards and in popular implementations are still positive integers in the range 0:p-1.

That's why seeing any negatives in documents can be confusing. Here are three cases that were confusing for me and I I think, they can be easily confusing for others as well.

  1. In this NIST document csrc.nist.gov/groups/ST/toolkit/documents/dss/NISTReCur.pdf you can find a criterea for choosing coefficient 'b' formulated as follows:

    $b^2 \cdot c = -27 \pmod p$

    It doesn't mean that there should be anything negative on the left side of this equation. '-27' simply means p - 27 here

    You can confirm this e.g. by doing simple math for P-160 in calc:

     ; p=6277101735386680763835789423207666416083908700390324961279
     ; c=0x3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65
     ; b=0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
     ; b^2*c%p
     ; p-27
  2. In RFC-5639 you can find $A = -3 \pmod p$, which actually means $p-3$ and you can confirm that using calc as well:

     ; p = 0xE95E4A5F737059DC60DFC7AD95B3D8139515620F
     ; a = 0xE95E4A5F737059DC60DFC7AD95B3D8139515620C;
     ; a%p
     ; p-3
  3. In EC points addition operator the last step is point mirroring over axis X and the most popular definition for that is:

    (Xr,Yr) -> (Xr,-Yr)

    Once again, it might not be clear what -Yr means here. It means a point, which is symmetric to Yr relatively to a median line parallel to the axis X. Where exactly that "median line" is located depends on a curve and its beta parameter. As you can see from the discussion below it's NOT necessary a median line for the Fp.

    I'm sharing all that for those who are confused with all those negative numbers in EC arithmetic, just like I was. When I was googling for something like "elliptic curves negative numbers", this was the only page that I've found.

  • $\begingroup$ where does that "- 0.5" come from? $\endgroup$ Commented Jun 17, 2015 at 16:36
  • $\begingroup$ p is a prime, thus always odd and p/2 is exactly 0.5 higher than the median if your Y coordinate starts at 0, e.g. 3/2 = 1.5 and a median is 1 (1.5 - 0.5). I do realize that all numbers are integers in a prime field Fp, so it's all just to simplify the calculation of the median Y and to visualize the Fp that helps me to understand EC arithmetic better. $\endgroup$
    – Oleg Gryb
    Commented Jun 17, 2015 at 19:19
  • $\begingroup$ for your "axis X ... at ... p/2 - 0.5", -x = p - x - 1. on the curve y² = x³ + 7 with p = 2²⁵⁶ - 2³² - 977 (secp256k1), the points with x = 1 have y = 85895366384747149408010284714111852077055649506395260922968891100383188440129 and y = 29896722852569046015560700294576055776214335159245303116488692907525646231534. if you add these two y values together, you get 0 mod p, not -1 mod p. $\endgroup$ Commented Jun 17, 2015 at 21:56
  • $\begingroup$ I was thinking about this today and realised that I couldn’t resolve a puzzle, because your example is absolutely correct and it means that your Y axis starts with 1, while mine starts with 0. The point symmetric to (1,0) is (1,p-1), right? But then it's (-1 mod p), not (0 mod p). We don't really need a curve to define symmetric points in Fp. What is wrong? Please explain. $\endgroup$
    – Oleg Gryb
    Commented Jun 18, 2015 at 6:05
  • $\begingroup$ Never mind, it's really simple - that median line for a curve can be shifted up or down depending on the coefficient beta, so it's different from the median line for Fp. I'll need to change the wording in the answer. $\endgroup$
    – Oleg Gryb
    Commented Jun 18, 2015 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.