# 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