Elliptic curve arithmetic

burrobert · 2012-11-06, 13:56

I am trying to locate the parts of gmp-ecm 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?

akruppa · 2012-11-06, 15:13

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.

burrobert · 2012-11-07, 13:48

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.

akruppa · 2012-11-07, 14:20

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 y-coordinate 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/en-us/...mon/thesis.pdf

burrobert · 2012-11-07, 21:54

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.

akruppa · 2012-11-08, 09:39

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.

burrobert · 2012-11-08, 13:05

ok thanks for clearing that point up.I'll have a look at the thesis.

2012-11-06, 13:56	#1
burrobert Oct 2012 Altona Victoria 1100₂ Posts	Elliptic curve arithmetic I am trying to locate the parts of gmp-ecm 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?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Elliptic-curve L-function question	fivemack	Math	0	2010-08-22 14:52
Elliptic Curve Arithmetic	Raman	Math	8	2009-04-13 19:20
Elliptic curve method	Dirac	Factoring	11	2007-11-01 14:01
Linear recurrence on elliptic curve	Unregistered	Information & Answers	2	2007-01-18 17:13
Elliptic factoring with points NOT on the curve	bongomongo	Factoring	5	2006-12-21 18:19

2012-11-06, 15:13	#2
akruppa "Nancy" Aug 2002 Alexandria 2,467 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.

2012-11-07, 13:48	#3
burrobert Oct 2012 Altona Victoria C₁₆ 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.

2012-11-07, 14:20	#4
akruppa "Nancy" Aug 2002 Alexandria 100110100011₂ 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 y-coordinate 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/en-us/...mon/thesis.pdf

2012-11-07, 21:54	#5
burrobert Oct 2012 Altona Victoria 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.

2012-11-08, 09:39	#6
akruppa "Nancy" Aug 2002 Alexandria 9A3₁₆ 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.

2012-11-08, 13:05	#7
burrobert Oct 2012 Altona Victoria 2²×3 Posts	ok thanks for clearing that point up.I'll have a look at the thesis.