Long ago, I saw a friend playing the 2048 game. One go at it, and I have been hooked on ever since. Sadly though, I haven't been able to get the 2048 tile and win it. It was really frustrating, so I decided to write an artificial intelligence to solve…
Some time back, I was working on some primality testing algorithms in the FLINT ulong_extras module (the Brillhart-Lehmer-Selfridge test to be precise). It required computing the cube root of the integer being tested. While implementing it, I realized that the ulong_extras module was missing a cube root function.…
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…
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…