mersenneforum.org > Math Need help with elliptic curves...
 Register FAQ Search Today's Posts Mark Forums Read

 2010-09-21, 03:38 #1 WraithX     Mar 2006 22×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: $y^2 = x^3 + 100*x$ 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?
2010-09-21, 06:55   #2
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

5·17·137 Posts

Quote:
 Originally Posted by WraithX 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?
A second component of zero represents the point at infinity in projective coordinates.

Paul

2010-09-21, 12:26   #3
WraithX

Mar 2006

22×7×19 Posts

Quote:
 Originally Posted by xilman A second component of zero represents the point at infinity in projective coordinates. Paul
Ah, that's good to know. There was mention in the book that:
"The point at infinity is recognized as the pair [0 : 0]"

So (just to be sure) for checking "point-at-infinity"-ness I only have to check the second component?

2010-09-21, 12:58   #4
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

5×17×137 Posts

Quote:
 Originally Posted by WraithX Ah, that's good to know. There was mention in the book that: "The point at infinity is recognized as the pair [0 : 0]" So (just to be sure) for checking "point-at-infinity"-ness I only have to check the second component?
Think about what the X:Z, Y:Z representation (i.e., projective co-ordinates) actually means ...

Paul

2010-09-22, 02:14   #5
WraithX

Mar 2006

22·7·19 Posts

Quote:
 Originally Posted by xilman Think about what the X:Z, Y:Z representation (i.e., projective co-ordinates) actually means ... Paul
Ok, I see that to get from projective to affine coordinates you divide by Z. Division by Z=0 is illegal, it doesn't matter the value of X or Y, so finding any point [X : 0] means you have a point at infinity.

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 $y^2 = x^3 + a*x + b$ (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?

2010-09-22, 21:40   #6
Random Poster

Dec 2008

2638 Posts

Quote:
 Originally Posted by WraithX 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?
Don't know about those in the first post, but these are obviously incorrect; if 5*P == 6*P, then P == 6*P - 5*P should (also) be the point at infinity.

 2010-09-22, 22:19 #7 fivemack (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) suggests that (in non-projective coordinates) 2P = [5776, -82308] 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 2010-09-22 at 22:20
 2010-09-22, 22:29 #8 fivemack (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 30-digit 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+1-ellap(E,n) t5=ellpow(e,z,npts/5) ellpow(e,t5,5) so t5 = [769304585007629536618026403584,375097933943672262837377836392] (or [296168060254308135503294009588,1] in your projective model) is a point which should give the point at infinity when you multiply it by 5.
2010-09-23, 01:04   #9
WraithX

Mar 2006

22×7×19 Posts

Quote:
 Originally Posted by fivemack 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.
Excellent, I tried figuring out how to do this with gp, but couldn't quite figure it out. Now I can use this to help with any troubleshooting in the future.

Quote:
 so t5 = [769304585007629536618026403584,375097933943672262837377836392] (or [296168060254308135503294009588,1] in your projective model) is a point which should give the point at infinity when you multiply it by 5.
When I multiplied P=[769304585007629536618026403584,375097933943672262837377836392] by 5, I did get a point at infinity. Specifically:
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 $X_- \neq 0$, that we may take"

The initial point for my curve above is P=[0,521284] (ie, $X_-=0$). Does anyone have an elliptic point addition algorithm that will work when given:
$P = [X_1 : Z_1]$
$k*P = [X_k : Z_k]$
$(k+1)*P = [X_{k+1} : Z_{k+1}]$
with $X_1 = 0$
and I want to find:
$(2k+1)*P$

or is there a way to modify the addh function from C&P so that it will work when $X_-=0$?

 2010-09-23, 03:32 #10 WraithX     Mar 2006 22×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.
 2010-09-26, 19:24 #11 WraithX     Mar 2006 22·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.

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 3 2017-11-15 20:23 burrobert GMP-ECM 6 2012-11-08 13:05 Raman Math 8 2009-04-13 19:20 wpolly GMP-ECM 5 2007-07-18 13:18 otkachalka Factoring 5 2005-11-20 12:22

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

Sat Jan 28 04:20:54 UTC 2023 up 163 days, 1:49, 0 users, load averages: 0.91, 0.99, 1.03