Need help with elliptic curves...

WraithX · 2010-09-21, 03:38

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?

xilman · 2010-09-21, 06:55

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

WraithX · 2010-09-21, 12:26

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?

xilman · 2010-09-21, 12:58

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

WraithX · 2010-09-22, 02:14

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?

Random Poster · 2010-09-22, 21:40

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.

fivemack · 2010-09-22, 22:19

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.

fivemack · 2010-09-22, 22:29

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.

WraithX · 2010-09-23, 01:04

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$ ?

WraithX · 2010-09-23, 03:32

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.

WraithX · 2010-09-26, 19:24

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.

2010-09-21, 03:38	#1
WraithX Mar 2006 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: $y^2 = x^3 + 100x$ 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? 2P = (90000, 40000) 3P = (158563240000000000, 1344800000000000) 4P = (23073610000000000000000, 2420640000000000000000) 5P = (58015789064385062459078, 172556051483969014783714) 10P = (224766984755015089030795, 89613043709746168630254) 20P = (63324287206147250700008, 66285572062524628896018) 30P = (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-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.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Testing Mersenne Primes with Elliptic Curves	a nicol	Math	3	2017-11-15 20:23
Elliptic curve arithmetic	burrobert	GMP-ECM	6	2012-11-08 13:05
Elliptic Curve Arithmetic	Raman	Math	8	2009-04-13 19:20
New coordinate system for elliptic curves	wpolly	GMP-ECM	5	2007-07-18 13:18
Elliptic curves in NFS	otkachalka	Factoring	5	2005-11-20 12:22

2010-09-23, 03:32	#10
WraithX Mar 2006 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.

2010-09-26, 19:24	#11
WraithX Mar 2006 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.