I started working on a simple MPQS this week. Most of the code required (Knuth Mutiplier, factor base, linear algebra, square root functions) was already available in the SIQS module, written/ported by Nitin. I just had to make small changes to the code to make it compatible with the…
Since I've missed out on some blog posts the last couple of weeks, I'll be summing up the stuff I've been up to in this post. The past month hasn't really been as productive as I would have wished, the reason being some wrong assumptions I made. I'll be giving…
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…
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…
Hi! I missed out last week's blog, couldn't write it as I was traveling and had poor internet connection. In the last two weeks, I have been trying out different implementations of stage II, using multi point evaluation. Mid term evaluations began on the 26th of June, and I have…
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,…
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…
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…
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…
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…