This week I started working on my GSoC project. Before starting off with the code, I decided to give three to four days understanding Pollard Rho and ECM once again. I was looking up for books in the IIITD library, when I came across Prime Numbers, A Computational Perspective. It was quite a pleasant surprise as I had been looking around for it for quite some time now, and was almost on the verge of ordering it. I have referred to this book quite a lot of times in the past, but had access only to a PDF version.
Another resource which I found quite useful, pointed out by my mentors was a paper published by Richard Brent, An Improved Monte Carlo Factorization Algorithm. It gives a detailed explanation of the modification Brent proposed to the Pollard Rho algorithm. The Pollard Rho was initially based on Floyd's cycle finding algorithm. Brent improved upon it by replacing the existing cycle finding algorithm by a better one.
I started off by implementing the Pollard Rho using standard FLINT big ints, fmpz_t's. This was split into two functions, an inner one which executed the algorithm with the polynomial constant and initial values as parameters, and an outer one, which assigned random values to the constant and initial value. The outer calls the inner a fixed number of times. The code can be found here.
Timings for the factorization can be found in the below pastes:
My only concern is that the current code fails a lot of times for smaller semi primes. This problem goes away if the inner is called 2 to 3 times. Moreover, I am not really worried about this as we would be using trial division for very small primes, which would cover these cases.
Next I tried implementing the same algorithm using mpn's. Those who don't know about mpn's, can read up on it over here. They are the lowest level GMP functions, which are designed to be as fast as possible. However getting used to them can be quite tricky.
The mpn layer is bare bones. They can be insanely fast however making mistakes is very very easy. I did make some mistakes while coding Pollard Rho using mpn's. probably the biggest of them was that I wasn't handling carries while using mpn_add_n(). Because of this, the polynomial evaluation was turning out to be wrong, and hence the algorithm was failing. The mpn code for Pollard Rho is currently in progress, however once I manage to implement it successfully, I think I will be quite at home with these functions. The code can be found here. In the next week, I plan to finish off Pollar Rho using mpn's, and then start off with ECM.