20100921, 03:38  #1 
Mar 2006
2^{2}×7×19 Posts 
Need help with elliptic curves...
Hello all,
I've written my own implementation of the ecm point multiplication from Crandall and Pomerance: Prime Numbers A Computational Perspective (Algorithm 7.2.7). I believe I have it working (for small multipliers), but it doesn't seem to be working with large multipliers. I've written this in GMP so there shouldn't be any worries about the number of bits in the multiplier. I was wondering if someone here could verify some point multiplications, or could point me to an online calculator that can help me verify my results? My elliptic curve is: with point P=(20,100) and I am working modulo N=465395381852899521743693 Algorithm 7.2.7 only works with (X,Z), so I believe that makes P=(20,1) Can someone verify if the following are true? 2*P = (90000, 40000) 3*P = (158563240000000000, 1344800000000000) 4*P = (23073610000000000000000, 2420640000000000000000) 5*P = (58015789064385062459078, 172556051483969014783714) 10*P = (224766984755015089030795, 89613043709746168630254) 20*P = (63324287206147250700008, 66285572062524628896018) 30*P = (372149390727801868323253, 185359676243647746065682) If the above are correct, then the reason I believe I am having a problem is from the following point multiplication: 465395381851553065610900*P = (95793308594731068161499, 0) I think it should give (0,0) [the point at infinity], but I am getting the above and can't figure out why. Have I fallen into some common pitfall? Are all my numbers above way off base? 
20100921, 06:55  #2  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
5·17·137 Posts 
Quote:
Paul 

20100921, 12:26  #3  
Mar 2006
2^{2}×7×19 Posts 
Quote:
"The point at infinity is recognized as the pair [0 : 0]" So (just to be sure) for checking "pointatinfinity"ness I only have to check the second component? 

20100921, 12:58  #4  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
5×17×137 Posts 
Quote:
Paul 

20100922, 02:14  #5  
Mar 2006
2^{2}·7·19 Posts 
Quote:
I am still curious if my computations of the point multiplications up above are correct? I have come across another curve and point that makes me doubt my implementation. The point is P=[0,521284,1] The curve is (mod n), with a=1409377777657316748665883636711 b=271737008656 n=1409377777657316748665962871879 When calculating k*P I get the following: 2*P = (6278211847988224, 1086948034624) 3*P = (0,0) 4*P = (862493446682833529002048409597, 365956753610466218478258974335) 5*P = (0,0) 6*P = (0,0) 7*P = (0,0) 8*P = (312380961781347960775073114289, 1101488459160176248242262341203) Can anyone verify if these numbers and the numbers from the first post are correct? 

20100922, 21:40  #6  
Dec 2008
263_{8} Posts 
Quote:


20100922, 22:19  #7 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
I would recommend testing your implementation against gp: 'ellinit' to set up the curve and 'ellpow' to perform point multiplication by an integer on it.
Code:
n=1409377777657316748665962871879 a=1409377777657316748665883636711 b=271737008656 a=Mod(a,n) b=Mod(b,n) e=ellinit([0,0,0,a,b]) z=[Mod(0,n),Mod(521284,n)] ellpow(e,z,2) 3P = [352344444414329187166490723114,176172222207164593583245375275] 4P = [1096182715955690804517971127065, 260995884751354953456659710813] So I agree with you for 2P (since 6278211847988224/1086948034624 = 5776) and 4P (since 862493446682833529002048409597/365956753610466218478258974335 == 1096182715955690804517971127065 mod n) but your figure for 3P is wrong. Last fiddled with by fivemack on 20100922 at 22:20 
20100922, 22:29  #8 
(loop (#_fork))
Feb 2006
Cambridge, England
2×7×461 Posts 
You can also use some of the more powerful machinery of GP: for example, count the points on E and use that to construct a point of small order. It's clear that n is special here since ellap completes instantaneously rather than taking the few minutes that it does for a random 30digit prime.
(I note that you have a=38^5 and b=38^8 / 2^4) Code:
n=1409377777657316748665962871879 a=1409377777657316748665883636711 b=271737008656 E=ellinit([0,0,0,a,b]) e=ellinit([0,0,0,Mod(a,n),Mod(b,n)]) z=[3,ellordinate(e,3)[1]] npts=n+1ellap(E,n) t5=ellpow(e,z,npts/5) ellpow(e,t5,5) 
20100923, 01:04  #9  
Mar 2006
2^{2}×7×19 Posts 
Quote:
Quote:
5*P = [49878016102633544070015433113: 0] So, I think my problem is based on a condition I am not meeting that is given as a prereq in C&P:PNaCP. The last line before specifying the formula for addh is: "then on the basis of Theorem 7.2.6 it is straightforward to establish, in the case that , that we may take" The initial point for my curve above is P=[0,521284] (ie, ). Does anyone have an elliptic point addition algorithm that will work when given: with and I want to find: or is there a way to modify the addh function from C&P so that it will work when ? 

20100923, 03:32  #10 
Mar 2006
2^{2}×7×19 Posts 
Actually, it looks like Algorithm 7.2.3 and 7.2.4 from C&P:PNaCP will be able to help me write a general point multiplication function. I'll report back when I have it implemented.

20100926, 19:24  #11 
Mar 2006
2^{2}·7·19 Posts 
Well, algorithms 7.2.3 and 7.2.4 from C&P were able to handle all my elliptic curve needs. Even when the initial point had x=0.
Thank you to xilman who helped me actually think about what these algorithms were doing. Thank you to fivemack for showing me how to use pari/gp to check my work. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing Mersenne Primes with Elliptic Curves  a nicol  Math  3  20171115 20:23 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
New coordinate system for elliptic curves  wpolly  GMPECM  5  20070718 13:18 
Elliptic curves in NFS  otkachalka  Factoring  5  20051120 12:22 