20190516, 02:45  #1 
May 2019
2^{3}×3 Posts 
SIQS diagnostics
Hello all, this is my first post on the forum.
I recently got interested in factoring while implementing some number theoryrelated programs in Clojure to teach myself the language. As far as algorithms go, I have managed to get as far as MPQS. My implementation is hardly competitive (the speed of the Alperton calculator blows my mind), but for a language that is not exactly known for speed, I'm quite satisfied with it right now. My MPQS implementation is based on this Python implementation (and it's faster than the CPython version—don't know about PyPy) and a bunch of papers. I recently tried to "upgrade" my MPQS to SIQS using Contini's paper and this Python implementation, but it's very slow. So far my MPQS beats the Python MPQS. But the Python SIQS (which was programmed by someone else) is slower than that, and my SIQS is slower still, for the same numbers. For example, a number that my MPQS could factor in a couple of seconds takes my SIQS 30 seconds or more. In both the Clojure and Python implementations, it seems like it has to run through way too many polynomials to pick up enough smooth relations. It's not uncommon for an entire cycle through a polynomial with a unique "a" and all of its "b"s to generate no smooth relations. If SIQS is supposed to be massively faster than MPQS, shouldn't just a couple of "brandnew" polynomials be enough? (Brandnew meaning a new "a" coefficient.) I did come across this thread where people mentioned that there was a typo in Contini's thesis. However, it is not clear to me what the typo actually is (and when I fiddled with the signs, it didn't make a difference). So my basic question is, what kind of gotchas should I look for with the polynomials to make sure they can capture as many smooth relations as possible? I have already verified that b^2 or (a  b)^2 is congruent to N mod a for each b. Other details of my implementation: In the sieving stage, I am ignoring small primes below some threshold, which is adjusted to compensate. The parameters for this were taken from the Python MPQS and they contribute to a significant speedup in SIQS as well. The Python SIQS uses a Monte Carlo method to generate the factors of "a", with the candidate pool restricted to primes between 400 and 4000. I've kept the same parameters in my implementation (tinkering with these bounds seems to make it take more time to generate an acceptable "a"—Contini's paper mentions that his minimum prime factor of "a" was >2000, but this seems crazy to me). As a side note, I'm testing on semiprimes that are considered "small" in the factoring world—40 to 50 digits—because I don't have time to sit around all day waiting for my program to finish 😅 Thanks! 
20190516, 08:15  #2 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{5}·5·37 Posts 
The aim with SIQS is to make switching polynomial very fast such that many more polynomials can be used than MPQS. However, I believe that my implementation still spends 10% of its time switching A. The more factors you have in A the less you will need to switch B, however, the factors get smaller the more you have and are excluded from sieving so they can't get too small.
Are you using large primes? At 50 digits I use about 11 As. This increases rapidly from here as numbers get bigger. Unless you are spending all your time generating them I wouldn't worry about having a few As. Each A had 6 factors allowing for 64 Bs per A. Last fiddled with by henryzz on 20190516 at 08:27 
20190516, 09:49  #3  
May 2019
2^{3}×3 Posts 
Quote:
Quote:


20190516, 10:01  #4  
May 2019
2^{3}·3 Posts 
Quote:
For that 40digit number I mentioned above, my As have 5 factors, generating 16 bs per A. (2^(51) = 16) Contini's paper says: Quote:
Last fiddled with by tabidots on 20190516 at 10:03 

20190516, 11:10  #5 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{5}×5×37 Posts 
I was wondering the same thing about the number of Bs per A. I will check that when I have more time. It would be nice if this turns into a factor of 2 improvement. My implementation never goes below 6 factors per A. The factors get smaller but it is worth it to need less As. Eventually MPQS or even QS get faster as the numbers get smaller due to this sort of issue.
The amount of As required may be fairly implementation dependent. For example my implementation is unusual in that it stores the sum of the logs of the found factors in enough precision that it is possible to work out the remaining factor(as long as it is <~53 bits) without having to refactor. This saves some time but uses more memory which means less cache efficiency. The large primes I referenced were remaining prime factors of x^2n larger than the factor base bound. These cost very little to collect and improve yield. A third of my relations are made by combining these. For 50 digits, my factor base bound is 60k but large primes will be accepted upto 2^23. For each polynomial I sieve a range of 600k. My SIQS is 2.3s for 50 digits. I think your factor base bounds is smaller than mine. I need around 1500 relations for 40 digits to your ~500. Again this is implementation dependent. 
20190516, 11:34  #6  
May 2019
24_{10} Posts 
Quote:
Quote:
My implementation filters the factor base for primes between 400 and 4000 (call them "candidates"), and accumulates random candidates until their product is greater than the "tipping point" (sqrt((maxcandidate  mincandidate) / 2)). It generates these until there are 30 that fall within plusorminus 10% of the ideal A, and chooses the one with the least error. In practice, the error of the A is 1% or less. It's not the fastest method, but the results are good (insofar as the obtained A is close to the ideal A) and the code is very clean—this sort of thing is quite legible and idiomatic in Clojure. I tried an alternate approach (as described in some other paper) to generate lexicographic combinations for the first `s2` Afactors and find the bestfitting product log for the last pair of Afactors. But it was much slower and very complicated. Quote:
I just generated a random 50digit semiprime (from two equalsized factors) (55720182748350551450373114705225729163236062899069). My MPQS generates these parameters: B = 5*(log_10(N))^2 ~= 12373.32, which ends up yielding a factor base of... #F = 725 primes, before including 1, so looking for 727 relations M = 60 * #F = 43500 (so sieving over a range of 87000 in total b/c positive & negative) 75s with MPQS. For SIQS I am using the #F parameter from msieve, and using that rather than B to constrain the factor base. So, for a 50digit number, that's 1200 primes (excluding 1). Many As are not generating smooths—sometimes even 10 in a row go by without any new smooths. Edited to add: I just switched out my parameters for yours in my MPQS and it did not make a huge difference—71s vs 75s—so that is indeed implementationdependent. Interesting! Last fiddled with by tabidots on 20190516 at 11:54 

20190516, 12:08  #7 
Tribal Bullet
Oct 2004
3·1,181 Posts 
tabidots is correct, k factors in A will generate 2^(k1) 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 k1 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 20190516 at 13:03 Reason: reword for clarity 
20190516, 12:13  #8  
May 2019
11000_{2} Posts 
Quote:


20190516, 18:58  #9  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{5}·5·37 Posts 
Quote:
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 20190516 at 19:02 

20190516, 19:33  #10  
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
2^{5}×5×37 Posts 
Quote:
Last fiddled with by henryzz on 20190516 at 19:35 

20190516, 20:06  #11  
"Ben"
Feb 2007
2·1,789 Posts 
Quote:
Quote:
Quote:
The value I use is obtained from a bunch of empirically determined magic numbers, loosely related to Contini's suggestion along the lines of: "compute the number of bits in M/2*sqrt(N/2), then subtract some slack". M is the size of your sieve interval. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
SIQS on GPU  cgy606  Factoring  1  20161021 13:37 
SIQS problems  henryzz  Factoring  2  20130826 23:02 
SIQS Problem  patrickkonsor  Factoring  3  20081020 12:03 
HELP! Online diagnostics  lythanhnguyen  Hardware  3  20070911 06:19 
Memory Diagnostics under XP?  R.D. Silverman  Hardware  3  20061117 16:06 