Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)?

share|improve this question
1  
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 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.