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.