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: [TEX]y^2 = x^3 + 100*x[/TEX] 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?

[QUOTE=WraithX;230718]
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?[/QUOTE]A second component of zero represents the point at infinity in projective coordinates.

Paul

[QUOTE=xilman;230727]A second component of zero represents the point at infinity in projective coordinates.

Paul[/QUOTE]

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?

[QUOTE=WraithX;230750]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?[/QUOTE]Think about what the X:Z, Y:Z representation (i.e., projective co-ordinates) actually means ...

Paul

[QUOTE=xilman;230759]Think about what the X:Z, Y:Z representation (i.e., projective co-ordinates) actually means ...

Paul[/QUOTE]

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

[QUOTE=WraithX;230835]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?[/QUOTE]
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.

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)
[/code]

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.

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)
[/code]

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.

[QUOTE=fivemack;230999]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.[/QUOTE]

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. [/QUOTE]

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 [TEX]X_- \neq 0[/TEX], that we may take"

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

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

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.

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.

Well, now that I've run algorithm 7.2.4 on numbers that I'll usually be working on, my implementation seems to be a little slow.

I'm wondering if anyone can point me to another algorithm that is faster than 7.2.4 from C&P? Either in a book or online would be fine. Or if you can post the algorithm here that'd be great too! ;)

Or can I use code from gmp-ecm? If this is okay, I'll try to create an implementation using ecm_mul from gmp-ecm's ecm.c. From there I can compare it speed wise to my code (I'm hoping for an order of magnitude speed up, or more!)

Also, in ecm.c, what is prac? Is it point multiplication code? Does the multiplier k have to be an int? Can it be an mpz_t? I'm doing some very large multiplications and an int definitely isn't large enough.

There's various work (Bernstein's papers on the hideously badly organised [url]http://cr.yp.to[/url] are a place to start) on making elliptic curve operations a bit more efficient. For exponentiation, you can get asymptotically up to a factor two by computing P, 3P, 5P, 7P ... and working through the exponent three or more bits at a time; since you've got subtraction on elliptic curves, writing the number in base -16 or similar can help. (if you ever found you needed to add an even multiple of P, you should have doubled one less time and added an odd multiple then)

prac does its operations using Lucas chains (ways to get to an integer by adding and subtracting previously-observed integers); I _think_ you could just rewrite it to use an mp_z for k and it would still work. It's full of weird mod-2 and mod-3 conditions.