20121106, 13:56  #1 
Oct 2012
Altona Victoria
14_{8} Posts 
Elliptic curve arithmetic
I am trying to locate the parts of gmpecm which deal with elliptic curve arithmetic such as addition and subtraction of points on curves. I can't find any reference to these in the documentation and have also looked through the various .c and .h files without success. Can anyone point me in the right direction please?

20121106, 15:13  #2 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
Some functions for arithmetic on curves in Montgomery form are in ecm.c, some functions for curves in Weierstrass form are in ecm2.c. The latter do batched additions, however, to save modular inverses.

20121107, 13:48  #3 
Oct 2012
Altona Victoria
2^{2}×3 Posts 
Thanks for that. I think I have located the relevant functions. As far as I can tell they are for special values of the curve parameters. For example the function add3 seems to apply to curves of the form gy^2 = x^3 + x. I can't work out what form of equation the doubling function 'duplicate' operates on. The value obtained for x2 suggests the curve is x^3 + x but the z2 value suggests otherwise.

20121107, 14:20  #4 
"Nancy"
Aug 2002
Alexandria
2467_{10} Posts 
Those functions operate on points on curves in Montgomery form. Those are in projective coordinates, so a point consists of the coordinates (x,y,z), but the arithmetic omits the ycoordinate and works only with (x:z). Montgomery's thesis is probably the best source for background on how arithmetic on curves of his form works, you can find it at http://research.microsoft.com/enus/...mon/thesis.pdf

20121107, 21:54  #5 
Oct 2012
Altona Victoria
2^{2}×3 Posts 
Yes I understand about Montgomery coordinates. I may be on the wrong track but add3 and duplicate appear to be implementations of the addh function as described by Crandall and POmerance. However the curve parameter a b c don't appear in add3 so presumably a particular choice of curve is being used. The same applies to the calculation of x2 in duplicate but not to z2.

20121108, 09:39  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Addition of points in Montgomery form does not use the curve parameter explicitly because that is implicit from the two input points and their difference (all of which are known to be on the curve) which are the inputs to add3(). The add3() function is a direct implementation of Equation (2.3.4) in Montgomery's thesis.

20121108, 13:05  #7 
Oct 2012
Altona Victoria
12_{10} Posts 
ok thanks for clearing that point up.I'll have a look at the thesis.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Ellipticcurve Lfunction question  fivemack  Math  0  20100822 14:52 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
Elliptic curve method  Dirac  Factoring  11  20071101 14:01 
Linear recurrence on elliptic curve  Unregistered  Information & Answers  2  20070118 17:13 
Elliptic factoring with points *NOT* on the curve  bongomongo  Factoring  5  20061221 18:19 