# 10 factors for x^2 coefficient in quadratic sieve?

I wrote a quadratic sieve and I tried plugging in all the same parameters as the wikipedia article says msieve uses: http://en.wikipedia.org/wiki/Quadratic_sieve#Parameters_from_realistic_example

It mentions that the number of prime factors used for generating $a$ in the polynomials is 10 (Using multiple prime factors gives more possible $b$ values for the same $a$ which allows you to skip certain initialization steps later on)

The number being factored is 277 bits and $a$ should optimally be about $\sqrt{2n}/M$ where $n$ is the number being factored and $M$ is the radius of the interval being sieved over (in this case $3*2^{16}$). Since $a$ is a square, the primes are multiplied together to get its square root so each prime is expected to be about $\sqrt{\sqrt{2n}/(3*2^{16})}^{1/10}$ which is about $((277+1)/2-17.6)/2/10 = 6$ bits. Since there are relatively few primes with only about 6 bits, how does msieve control their product well enough to keep it in the optimal range (considering that it has to generate hundreds of these $a$'s, each one distinct)?

-
Warning: I edited to put in some TeX but I'm not sure I got everything right. – Gerry Myerson Jul 26 '11 at 23:19

## 1 Answer

The self-initializing variant of MPQS doesn't take a square root to estimate the size of 'a' values, so the primes making up 'a' can be maybe 9-12 bits in size.

Actually Msieve goes to a lot of trouble to find a random collection of primes that multiply out to very nearly the optimal 'a' value. With a large enough of candidate primes (say, 50 of them) you can produce millions of 'a' values and still be very unlikely to pick a duplicate 'a' at random.

-