mersenneforum.org Elliptic curve arithmetic
 Register FAQ Search Today's Posts Mark Forums Read

 2012-11-06, 13:56 #1 burrobert     Oct 2012 Altona Victoria 148 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?
 2012-11-06, 15:13 #2 akruppa     "Nancy" Aug 2002 Alexandria 1001101000112 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 22·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.
 2012-11-07, 14:20 #4 akruppa     "Nancy" Aug 2002 Alexandria 2,467 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 22·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 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.
 2012-11-08, 13:05 #7 burrobert     Oct 2012 Altona Victoria 11002 Posts ok thanks for clearing that point up.I'll have a look at the thesis.

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack Math 0 2010-08-22 14:52 Raman Math 8 2009-04-13 19:20 Dirac Factoring 11 2007-11-01 14:01 Unregistered Information & Answers 2 2007-01-18 17:13 bongomongo Factoring 5 2006-12-21 18:19

All times are UTC. The time now is 20:43.

Wed May 12 20:43:50 UTC 2021 up 34 days, 15:24, 1 user, load averages: 1.56, 1.93, 2.10