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

Improve this question
15
  • 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, 2014 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, 2014 at 22:38
  • 1
    Sorry, I just mean a URL to the description of the algorithm.
    – Nate Eldredge
    Jun 15, 2014 at 22:41
  • 1
    you use ph1^2 which is XOR in C++, you should write ph1*ph1,
    – Willem Hengeveld
    Jun 18, 2014 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, 2014 at 9:33

1 Answer 1

Reset to default
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.

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

Your Answer

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

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