View Single Post
Old 2019-05-16, 12:08   #7
Tribal Bullet
jasonp's Avatar
Oct 2004

3×1,181 Posts

tabidots is correct, k factors in A will generate 2^(k-1) polynomials to sieve. Each factor has 2 roots (a positive and negative root) to contribute to each B, but if you generated all 2^k combinations the B values from all the negative roots are just the negative of the B values from the positive roots, so you would find the same relations twice. So in practice you can pick the first root, force it to be positive, then enumerate all combinations of the other k-1 roots.

Contini showed that if the time for switching A values was neglected and the size of polynomial coefficients and sieving interval was chosen optimally, you would expect to accumulate relations twice as fast as with MPQS, so that's the maximum speedup I would expect. The lower overhead allows the sieving interval to be much smaller for SIQS, which is what improves the probability of finding relations (the size of numbers to factor increases with larger sieving interval).

Debugging the sieving when only a few relations are found is extremely difficult. I would start with maintaining the full value of each A, B and C, verifying that repeated B do not appear, then finding the values mod each prime in the factor base and verifying that your starting sieve roots (after all setup is complete) cause the polynomial to be zero. Note also that for MPQS all B are positive but for SIQS it is possible to have negative B.

This process is what led me to believe that Contini's thesis has a typo in the arithmetic for computing the next B given the previous one; instead of adding the next root you have to subtract it.

Last fiddled with by jasonp on 2019-05-16 at 13:03 Reason: reword for clarity
jasonp is offline   Reply With Quote