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.