Google Summer of Code 2015

The Google Summer of Code results came out this week, and I got selected :D. Thanks to lmonade for giving me this amazing opportunity. I would be writing code for FLINT over the summer, mentored by William Hart and Dana Jacobsen.

FLINT is a fast number theory library written in C. Over the summer, I would be working on big integer factorization algorithms for FLINT. Currently, FLINT lacks a robust module for the same. For smooth numbers and "smaller" numbers, there exists a fast implementation of the William's p + 1 algorithm, however it cannot be used for larger numbers.

My goal would be to factorize a 60 digit number in 8 seconds, and a 100 digit number in under a day, on a single core. To ahieve this, I would be implementing an advanced variant of the Multiple Polynomial Quadratic Sieve (the double large variant), and along with it a very basic version of the Elliptic Curve Factorization method which would be used in the MPQS. There is a QS present in FLINT, however it has some problems associated with it.

Quadratic Sieves can be made very efficient, and can take up a lot of time to implement. I have heard of a person, who spent over 10 years working on an implementation. Some of his code has also been used in the current QS in FLINT. This year two students have been selected for implementing the QS. The work has been divided into two halfs. The first project is to implement a self initializing MPQS, and the second to implement the double large prime variant, and possibly the triple large prime variant. Hopefully at the end of GSoC 2015, these two halfs of the QS will be ready, and merged into one. I would be working on the latter project.

I am looking forward to the summer and hope to learn a lot from it. If someone wishes to read, my proposal can be found here.

Show Comments