mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-09-21, 03:38   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

1D816 Posts
Default 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?
WraithX is offline   Reply With Quote
Old 2010-09-21, 06:55   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,253 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
xilman is online now   Reply With Quote
Old 2010-09-21, 12:26   #3
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
WraithX is offline   Reply With Quote
Old 2010-09-21, 12:58   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

10,253 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
xilman is online now   Reply With Quote
Old 2010-09-22, 02:14   #5
WraithX
 
WraithX's Avatar
 
Mar 2006

23·59 Posts
Default

Quote:
Originally Posted by xilman View Post
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?
WraithX is offline   Reply With Quote
Old 2010-09-22, 21:40   #6
Random Poster
 
Random Poster's Avatar
 
Dec 2008

179 Posts
Default

Quote:
Originally Posted by WraithX View Post
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.
Random Poster is offline   Reply With Quote
Old 2010-09-22, 22:19   #7
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18D616 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2010-09-22, 22:29   #8
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2×11×172 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2010-09-23, 01:04   #9
WraithX
 
WraithX's Avatar
 
Mar 2006

1D816 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 is offline   Reply With Quote
Old 2010-09-23, 03:32   #10
WraithX
 
WraithX's Avatar
 
Mar 2006

47210 Posts
Default

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 is offline   Reply With Quote
Old 2010-09-26, 19:24   #11
WraithX
 
WraithX's Avatar
 
Mar 2006

1110110002 Posts
Default

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.
WraithX is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 16:01.

Fri Sep 25 16:01:31 UTC 2020 up 15 days, 13:12, 1 user, load averages: 1.62, 1.54, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.