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 sieve I am writing. The part which I had to write again was the polynomial code. It wasn't that tough as self initialization was not required.
The polynomial I am using in the sieve is Q(x) = (Ax + B)^2. Hence, we have to solve the equation Q(x) - kN = 0, i.e. A^2x^2 + 2ABx + B^2 - kN = 0.
While evaluating, we pull the factor A out, and try to factor Ax^2 + 2Bx + (B^2 - kN)/A. So for evaluating the sieve at different positions, we have to compute A, B, and C (C equals B^2 - kn).
I am using this paper as a reference. The ideal value of A is the square of a prime d near the value (N/(2 * M^2))^1/4. B is chosen as the odd square root of kN (mod A). This is done by first calculating the square root mod d (which is a prime), and then using Hensel lifting to calculate the square root mod A (which is d^2). C can be computed easily by computing (B^2 - kN)/A.
d^2). C can be computed easily by computing (B^2 - kN)/A.
I have coded a couple of functions which implement selecting multiple polynomials and computing associated data, the most important being the roots of Q(x) = N (mod p), for each prime p in the factor
- Functions to compute A, B &
- Functions to compute the Q(x) = N mod p for each prime p in the factor
- Function to initialize
- Function to compute the next polynomial
The code can be found in this file.
I also ported the code from the existing SIQS module for MPQS module. The current implementation has some problems, it does not factor. The control never reaches inside the mpqs_evaluate_candidate() function. Hence no relations are found. I am looking into this problem currently.