1

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

  • 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? – Nate Eldredge Jun 15 '14 at 22:36
  • Wow, first response and its already challenged my limited understanding of c++. how would I make it a ..."pointer"? – Mine Jun 15 '14 at 22:38
  • 1
    Sorry, I just mean a URL to the description of the algorithm. – Nate Eldredge Jun 15 '14 at 22:41
  • 1
    you use ph1^2 which is XOR in C++, you should write ph1*ph1, – Willem Hengeveld Jun 18 '14 at 9:30
  • and you use way to many brackets. and the %p applies only to (gx1 + gx2), not to the whole expression – Willem Hengeveld Jun 18 '14 at 9:33
2

The magic phrase on that page is in a 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). 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. Of course, you will also need to be using 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.

  • So basically there is no single short simple method by which to achieve this? – Mine Jun 15 '14 at 23:16
  • 2
    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 Jun 16 '14 at 0:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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