Need help with elliptic curves... - Page 2

WraithX · 2010-09-29, 01:51

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.

fivemack · 2010-09-29, 09:34

There's various work (Bernstein's papers on the hideously badly organised http://cr.yp.to 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.

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-29, 01:51	#12
WraithX Mar 2006 2·277 Posts	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.

2010-09-29, 09:34	#13
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 1936₁₆ Posts	There's various work (Bernstein's papers on the hideously badly organised http://cr.yp.to 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.