The official coding period for GSoC begins tomorrow, and I plan to start off with ECM, before beginning with the MPQS implementation. I think it would be better to have both the auxiliary factoring algorithms in hand before I proceed with the MPQS. I spent most of the community bonding period getting used to the fmpz module and MPN layer functions of FLINT and GMP, and implemented the Pollard Rho algorithm.
The previous week I finished off with the Pollard Rho implementation. Along with the mpn layer code I was working on, I also implemented it using
mp_limb_t's for one word inputs. It turns out to be five to six times faster for one word integers, compared to the fmpz_t code.
Currently, there is a
fmpz_factor_pollard_brent() in the fmpz_factor module, which calls the ulong version of Pollard Brent (available in the ulong_extras module) for one word integers, and the mpn code for bigger integers. There is also a function
fmpz_factor_pollard_brent_single() present in the fmpz_factor module, which lets the user pass initial parameters (the constant of the polynomial and the initial value to start evaluation with) for Pollard Brent.
This week I also read some basic elliptic curve theory. I followed Prime Numbers, A Computational Perspective by Crandall and Pomerance for this purpose. I understood the various coordinate representations and the group operation addition, however I still have some doubts regarding addition of coordinates when represented in the Montgomery form. I haven't gone through it thoroughly, however I noticed Lucas Chains being mentioned somewhere, and this part confused me. The book had a good explanation of addition of affine and Projective coordinates, however I couldn't find such an article on Montgomery coordinates.
This week, I plan to understand addition and scalar multiplication of Montgomery coordinates, and implement them. Once this is done, I can start off with phase I of the ECM. I also plan to go through the source code of pyecm and GMP-ECM. Although pyecm is in python and not in C, it still might help me give some ideas about the implementation.
I received the welcome package from Google yesterday, and the goodies are amazing!! The package had a sticker, a red diary and a pen. The sticker's awesome, they just keep getting better every year. Let the coding begin :D