View Single Post
Old 2019-05-16, 18:58   #9
Just call me Henry
henryzz's Avatar
Sep 2007
Cambridge (GMT/BST)

10111001000002 Posts

Originally Posted by jasonp View Post
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.
This leads me to wonder why I am not drowning in duplicate relations. I do get some but very few. I was assuming this was me finding x^2-N and (-x)^2-N
I wonder if this is something to do with me not changing the centre of my sieving range when I change B.
I do end up having both B and -B in my list of Bs. Is it these you are suggesting should have the same relations?
I end up sieving twice as many As if I don't sieve the second half of the Bs for each A. I do completely loose all duplicates though. Something strange is going on.

Last fiddled with by henryzz on 2019-05-16 at 19:02
henryzz is offline   Reply With Quote