2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Warning: I edited to put in some TeX but I'm not sure I got everything right. $\endgroup$ Jul 26, 2011 at 23:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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