mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2012-11-06, 13:56   #1
burrobert
 
burrobert's Avatar
 
Oct 2012
Altona Victoria

22·3 Posts
Default 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?
burrobert is offline   Reply With Quote
Old 2012-11-06, 15:13   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-11-07, 13:48   #3
burrobert
 
burrobert's Avatar
 
Oct 2012
Altona Victoria

22·3 Posts
Default

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.
burrobert is offline   Reply With Quote
Old 2012-11-07, 14:20   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2012-11-07, 21:54   #5
burrobert
 
burrobert's Avatar
 
Oct 2012
Altona Victoria

C16 Posts
Default

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.
burrobert is offline   Reply With Quote
Old 2012-11-08, 09:39   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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.
akruppa is offline   Reply With Quote
Old 2012-11-08, 13:05   #7
burrobert
 
burrobert's Avatar
 
Oct 2012
Altona Victoria

11002 Posts
Default

ok thanks for clearing that point up.I'll have a look at the thesis.
burrobert is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 19:18.

Fri May 7 19:18:52 UTC 2021 up 29 days, 13:59, 0 users, load averages: 2.32, 2.40, 2.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.