FLINT ECM for large integers

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…

Rewriting the FLINT ECM

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…

GSoC update - Week III

The past week, I optimized the current stage II, and tried out a new version of stage II ECM. The main way by which we can optimize stage II is by reducing the number of points we compute. My mentor pointed out a very nice way to do so. Unfortunately,…

ECM Stage II

I spend the larger half of last week studying elliptic curves and understanding possible stage II extensions, rather than coding. I got stuck at a lot of places and had to read a lot to understand. Implementing stage II was certainly harder than stage I. More on that a bit…

Implementing the ECM Stage I in FLINT

This week I tried implementing the Elliptic Curve Method of Factorization. I spent most of the time trying to understand how the algorithm works, and going through existing implementations (GMP-ECM and pyECM). After spending quite some time, I decided to stick to the Montgomery elliptic curve coordinates for the stage…