I spent the last week rewriting the ECM using mpn's and pre-computed inverses, and ulongs. Pollard Rho did show a significant speedup when I rewrote it using mpn's and pre-computed inverses, and I was hoping for the same here. Initially I was planning to write only till stage I using the faster options available, however I ended up working on both stage I and stage II.
The flow which I had in mind was similar to many existing functions in FLINT. If the integer to be factorized fits in one word, use the ulong module else use fmpz's/mpn's. So I decided to rewrite ECM using the ulong module first.
The ulong version code :
- Group Addition of co-ordinates
- Group Double of co-ordinates
- Group Scalar Multiplication of co-ordinates
- Function to select Curve Parameters
- ECM Stage I
- ECM Stage II
- Outer wrapper function for ECM
Next I attempted to write ECM using mpn's. The code which I have written so far (using mpn's) works fine for single word integers, however causes problems for larger integers. It is still work in progress.
The current version of ECM still has a lot of room for improvement. This includes tuning it so as to find optimal values for B1 and B2. Also I still haven't been able to pinpoint my error in the multipoint evaluation stage II I wrote a couple of weeks back. It works, however is slightly slower than than the initial stage II.
What I plan for this
- Figure out what's causing problems for integers larger than one word in the mpn version of ECM and finish writing
- Time ECM against GMP
- Understand the double prime QS more thoroughly, go thorough the QS which Nitin (who is working on the SIQS) has written and start writing a double prime version using it.