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.