<p>The magic phrase on that page is <em>in a <a href="http://en.wikipedia.org/wiki/Finite_field" rel="nofollow">finite field</a></em>.  Here the finite field is the integers mod p, where p is the number 2<sup>256</sup> - 2<sup>32</sup> - 2<sup>9</sup> - 2<sup>8</sup> - 2<sup>7</sup> - 2<sup>6</sup> - 2<sup>4</sup> - 1 (see <a href="https://en.bitcoin.it/wiki/Secp256k1" rel="nofollow">here</a>).  So all the arithmetic in your equations isn't ordinary arithmetic of integers or real numbers; it needs to be done mod p.   See <a href="http://en.wikipedia.org/wiki/Modular_arithmetic" rel="nofollow">http://en.wikipedia.org/wiki/Modular_arithmetic</a>.  For addition, subtraction and multiplication, you can use ordinary integer arithmetic and compute the remainder mod p at the end.  For division, you will need something like the <a href="http://en.wikipedia.org/wiki/Extended_euclidean_algorithm" rel="nofollow">extended Euclidean algorithm</a>.  Of course, you will also need to be using <a href="http://en.wikipedia.org/wiki/Arbitrary_precision_arithmetic" rel="nofollow">arbitrary precision arithmetic</a> if you are not already, since numbers of this size are much too large for standard C++ types like <code>long int</code> and <code>double</code>.</p>

CC BY-SA 3.0
2014-06-15T23:16:29.917Z
So basically there is no single short simple method by which to achieve this?
Mine
CC BY-SA 3.0
2014-06-16T00:34:33.200Z
No, I don't believe there are any shortcuts that simplify it significantly more than what you've already read.  In particular, you can't avoid the use of modular arithmetic.
Nate Eldredge
CC BY-SA 3.0
2014-06-15T23:05:49.807Z
2014-06-15T23:05:49.807Z
Nate Eldredge
<p>I've been implementing point addition into a c++ program I've written but I don't see how this can be done right.  When I do <code>slope = (y1 - y2)/(x1 - x2)</code> I get a freaking decimal, which doesn't produce the proper points when applied to the other parts of the equation due to  it not retaining its fractional qualities.  Anyone have any ideas how how to get past that?</p>

<p>Point Addition being defined by the following equation:</p>

<pre><code>slope = (y1 - y2) / (x1 - x2)

xsum = slope ^ 2 - (x1 + x2)

ysum = slope * (x1 - xsum) - y1
</code></pre>

<p>Whereby Private Address x02 with x,y coordinates respectively:</p>

<pre><code>89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930
</code></pre>

<p>with the Point Addition of Private Address x01 with x,y coordinates respectively:</p>

<pre><code>55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424
</code></pre>

<p>applied to the above equation produce the result of Private Address x03 with x,y coordinates respectively:</p>

<pre><code>112711660439710606056748659173929673102114977341539408544630613555209775888121
25583027980570883691656905877401976406448868254816295069919888960541586679410
</code></pre>

<p><a href="http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication" rel="nofollow">http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication</a></p>

<p>EDIT:</p>

<p>I put this C++ program together, and I've modified in every way I can think of (moving %p around, doing it too many times, breaking up the equations and the like).  I can't get it to result in the proper results.  Anyone mind checking it out and see what you can find please?</p>

<p><a href="http://coliru.stacked-crooked.com/a/26f9ed24ed5a86ed" rel="nofollow">http://coliru.stacked-crooked.com/a/26f9ed24ed5a86ed</a></p>

CC BY-SA 3.0
2014-06-15T22:36:01.780Z
You should probably give a pointer to the description you're reading, since those I have seen don't have anything called slope.  At a guess, though, perhaps the division is meant to be done using modular arithmetic?
Nate Eldredge
CC BY-SA 3.0
2014-06-15T22:38:53.693Z
Wow, first response and its already challenged my limited understanding of c++.  how would I make it a ..."pointer"?
Mine
CC BY-SA 3.0
2014-06-15T22:41:36.137Z
Sorry, I just mean a URL to the description of the algorithm.
Nate Eldredge
CC BY-SA 3.0
2014-06-18T09:30:29.420Z
you use  ph1^2  which is XOR in C++,  you should write ph1*ph1,
Willem Hengeveld
CC BY-SA 3.0
2014-06-18T09:33:44.080Z
and you use way to many brackets. and the %p applies only to (gx1 + gx2), not to the whole expression
Willem Hengeveld
CC BY-SA 3.0
2014-06-18T09:46:25.370Z
and you use unsigned ints, i think you need signed integers.
Willem Hengeveld
CC BY-SA 3.0
2014-06-18T10:43:02.640Z
and the while (a>1) in your mul_inv  should be: while (b!=0)
Willem Hengeveld
CC BY-SA 3.0
2014-06-18T14:01:34.507Z
On the bottom right corner of the website there is an "edit" button anyone can use to try it (then you compile and share it, the share will produce a new url u can share).  http://coliru.stacked-crooked.com/a/7368ec065cd78b8c is the newest one.  I tried all your suggestions (any many variations thereof) to no avail.
Mine
CC BY-SA 3.0
2014-06-19T02:25:36.217Z
http://coliru.stacked-crooked.com/a/3f9112304c3c9c44
Willem Hengeveld
CC BY-SA 3.0
2014-06-19T05:22:31.050Z
Wilem, tyvm, I can't even make sense of why one of my variations didn't work (as I "know" I tried that).  Maybe I'm making a mistake where my programs aren't compiling in an updated form or something....  would you by chance mind showing me how you'd get the proper y coordinate too in that program?  i really don't understand it; but mine isn't working for the y value.
Mine
CC BY-SA 3.0
2014-06-19T05:43:15.913Z
http://coliru.stacked-crooked.com/a/fdaee6a813614d51
Mine
CC BY-SA 3.0
2014-06-19T06:02:48.577Z
Okay, I got it....I don't get why I had to do y2 = (ph1 * gx1) - (ph1 * x2) - gy1 with %p of each parenthesis rather than y2 = ph1 * (gx1 - x2) - y1 and then y2 %= p.
Mine
CC BY-SA 3.0
2014-06-19T10:50:20.613Z
your ph1 result somehow has the wrong sign,  if you replace it with 'p-ph1'  you do arrive at the correct result.  maybe something is wrong with your mul_inv still?
Willem Hengeveld
CC BY-SA 3.0
2014-06-21T08:06:20.307Z
That seems possible suddenly, I just checked some of my results, the program spits out the proper x,y coordinates for only a couple addresses.  It suddenly gets the wrong y coordinate, then that skews all subsequent values. I'm assessing it further
Mine
CC BY-SA 3.0
2014-06-21T09:22:27.870Z
http://coliru.stacked-crooked.com/a/74648b16c2692525 Resulting values of x are valid up to 0x05, at 0x06 they are wrong.  Values of y are only valid for 0x03, and for no others.
Mine
<development><protocol><ecdsa>
Programming and the ECDSA equation
Mine
# Programming and the ECDSA equation

(Asked by: username_0 on 2014-06-15)

I've been implementing point addition into a c++ program I've written but I don't see how this can be done right. When I do `slope = (y1 - y2)/(x1 - x2)` I get a freaking decimal, which doesn't produce the proper points when applied to the other parts of the equation due to it not retaining its fractional qualities. Anyone have any ideas how how to get past that?

Point Addition being defined by the following equation:

```
slope = (y1 - y2) / (x1 - x2)

xsum = slope ^ 2 - (x1 + x2)

ysum = slope * (x1 - xsum) - y1

```

Whereby Private Address x02 with x,y coordinates respectively:

```
89565891926547004231252920425935692360644145829622209833684329913297188986597
12158399299693830322967808612713398636155367887041628176798871954788371653930

```

with the Point Addition of Private Address x01 with x,y coordinates respectively:

```
55066263022277343669578718895168534326250603453777594175500187360389116729240
32670510020758816978083085130507043184471273380659243275938904335757337482424

```

applied to the above equation produce the result of Private Address x03 with x,y coordinates respectively:

```
112711660439710606056748659173929673102114977341539408544630613555209775888121
25583027980570883691656905877401976406448868254816295069919888960541586679410

```

<http://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication>

EDIT:

I put this C++ program together, and I've modified in every way I can think of (moving %p around, doing it too many times, breaking up the equations and the like). I can't get it to result in the proper results. Anyone mind checking it out and see what you can find please?

<http://coliru.stacked-crooked.com/a/26f9ed24ed5a86ed>

**Tags:** development, protocol, ecdsa

> **Comments:**
> **username_1**: You should probably give a pointer to the description you're reading, since those I have seen don't have anything called slope.  At a guess, though, perhaps the division is meant to be done using modular arithmetic?  
> **username_0**: Wow, first response and its already challenged my limited understanding of c++.  how would I make it a ..."pointer"?  
> **username_1**: Sorry, I just mean a URL to the description of the algorithm.  
> **username_2**: you use  ph1^2  which is XOR in C++,  you should write ph1*ph1,  
> **username_2**: and you use way to many brackets. and the %p applies only to (gx1 + gx2), not to the whole expression  
> **username_2**: and you use unsigned ints, i think you need signed integers.  
> **username_2**: and the while (a>1) in your mul_inv  should be: while (b!=0)  
> **username_0**: On the bottom right corner of the website there is an "edit" button anyone can use to try it (then you compile and share it, the share will produce a new url u can share).  http://coliru.stacked-crooked.com/a/7368ec065cd78b8c is the newest one.  I tried all your suggestions (any many variations thereof) to no avail.  
> **username_2**: http://coliru.stacked-crooked.com/a/3f9112304c3c9c44  
> **username_0**: Wilem, tyvm, I can't even make sense of why one of my variations didn't work (as I "know" I tried that).  Maybe I'm making a mistake where my programs aren't compiling in an updated form or something....  would you by chance mind showing me how you'd get the proper y coordinate too in that program?  i really don't understand it; but username_0 isn't working for the y value.  
> **username_0**: http://coliru.stacked-crooked.com/a/fdaee6a813614d51  
> **username_0**: Okay, I got it....I don't get why I had to do y2 = (ph1 * gx1) - (ph1 * x2) - gy1 with %p of each parenthesis rather than y2 = ph1 * (gx1 - x2) - y1 and then y2 %= p.  
> **username_2**: your ph1 result somehow has the wrong sign,  if you replace it with 'p-ph1'  you do arrive at the correct result.  maybe something is wrong with your mul_inv still?  
> **username_0**: That seems possible suddenly, I just checked some of my results, the program spits out the proper x,y coordinates for only a couple addresses.  It suddenly gets the wrong y coordinate, then that skews all subsequent values. I'm assessing it further  
> **username_0**: http://coliru.stacked-crooked.com/a/74648b16c2692525 Resulting values of x are valid up to 0x05, at 0x06 they are wrong.  Values of y are only valid for 0x03, and for no others.  

---

## 1 answers

### Answer by username_1 on 2014-06-15. Score: 2

The magic phrase on that page is *in a [finite field](http://en.wikipedia.org/wiki/Finite_field)*. Here the finite field is the integers mod p, where p is the number 2256 - 232 - 29 - 28 - 27 - 26 - 24 - 1 (see [here](https://en.bitcoin.it/wiki/Secp256k1)). So all the arithmetic in your equations isn't ordinary arithmetic of integers or real numbers; it needs to be done mod p. See <http://en.wikipedia.org/wiki/Modular_arithmetic>. For addition, subtraction and multiplication, you can use ordinary integer arithmetic and compute the remainder mod p at the end. For division, you will need something like the [extended Euclidean algorithm](http://en.wikipedia.org/wiki/Extended_euclidean_algorithm). Of course, you will also need to be using [arbitrary precision arithmetic](http://en.wikipedia.org/wiki/Arbitrary_precision_arithmetic) if you are not already, since numbers of this size are much too large for standard C++ types like `long int` and `double`.

> **Comments:**
> **username_0**: So basically there is no single short simple method by which to achieve this?  
> **username_1**: No, I don't believe there are any shortcuts that simplify it significantly more than what you've already read.  In particular, you can't avoid the use of modular arithmetic.  

---

