This week I finished writing ecm using the mpn functions and reduction using pre-computed inverse for integers larger than one word. The code is present in these files:
- ECM structure init
- ECM structure clear
- Addition on curve
- Doubling on curve
- Scalar multiplication of a point on curve (Montgomery Ladder)
- Function to select Curve Parameters
- ECM stage I
- ECM stage II
- ECM outer function
Apart from these, I also wrote a couple of helper functions for mpn arithmetic:
These are not regular functions, and cannot be used with all elliptic points. These assume that the "n" passed has its highest bit set. I did this to save a couple of additions. We are anyway working with normalized (shifted) mpn's, and hence don't cause a problem.
Documentation and tests for fmpz_factor_ecm() is present here:
The current ECM is doing a good job, it takes around 0.1 to 0.2 seconds on an average to find a 50 bit factor (~15 digits). I never got around to finding why using multi point polynomial evaluation was slowing down stage II, whereas theoretically it should have been faster. I'll probably look at it later on. Also, I haven't profiled it and found optimum parameters (B1 & B2) for different sized factors. These two things ought to speed it up further.
Another problem, or rather a code inconsistency exists in the fmpz_factor_ecm_select_curve() function. I was having some trouble using mpn_gcdext() at one point, so I am converting back to fmpz_t, using fmpz_gcdinv(), and then converting back to mp_ptr. This works, although it's quite hacky. I'll figure out the right way to use mpn_gcdext() and alter it.
The only serious problem, is that the current ECM implementation cannot find factors below 7 bits. The fmpz_factor_ecm_select_curve() function fails to find a suitable curve for such integers.
Another thing I worked upon is n_factor() in the ulong_extras module. Brent-Pollard Rho and ECM seem to do a better job than SQUFOF, which is used currently. So instead of just calling factor_one_line() and SQUFOF, I changed it so that it calls Brent-Pollard Rho once, and then ECM for some tries. This gives almost a 4 to 5 time speedup when factoring semi primes, and 1.5 to 2 times for random cases. SQUFOF is still there in the code, so as to make sure that n_factor doesn't fail (in case Brent Pollard Rho and ECM do), however I never saw it being called in all the random cases I tried.
Including Brent-Pollard Rho and ECM did cause a problem though. Both of them require random states to be passed, and changing the function definition of n_factor() will break existing FLINT code. My mentor suggested that we should cache a flint_rand_t in the factor function itself. I am working on this right now.
This week, I plan to finish the small part remaining in n_factor() (caching of the flint_rand_t) and then go back to double large prime MPQS. I am using the paper MPQS with three large primes as a reference. Although named three large primes, it also gives quite a lot of information on the double large prime version.