20190518, 08:55  #23 
Just call me Henry
"David"
Sep 2007
Cambridge (GMT/BST)
5922_{10} Posts 
I implemented based on https://www.rieselprime.de/ziki/Self...uadratic_sieve rather than Contini's thesis. This might be slightly clearer.

20190518, 10:45  #24  
May 2019
2^{3}×3 Posts 
Quote:
Well, I am still tinkering with my SIQS, because I feel I am really close. Definitely feeling the sunkcost effect at this point, as I have been slaving away at this for a couple weeks now. I have figured out the whole sign issue. It affects the calculation of the subsequent s, not the subsequent s. So, this is correct, as per Contini: But the s involve subtracting from, not adding to, the previous : After I incorporated this, I was able to successfully verify:
It picks up relations quite quickly compared to before, and they pass the tests above. But I am still not finding factors, which is really puzzling—after the polynomials, I'm using the exact same code as for MPQS (being sure to refactor in the factoredout values at the end). Last fiddled with by tabidots on 20190518 at 10:45 

20190518, 11:53  #25 
May 2019
24_{10} Posts 
Here is something really bizarre. I sprinkled some assertions in my MPQS functions to ensure that
My MPQS fails the first assertion and passes the second, succeeding in finding a factor. My SIQS passes the first assertion and fails the second, failing to find a factor. A real headscratcher! 
20190518, 14:05  #26 
May 2019
2^{3}×3 Posts 
I've discovered the (a?) reason my SIQS currently struggles to find a factor is that it produces an abundance of duplicate relations. I'll have to rework the Agenerating algorithm. Too bad—the Monte Carlo code was so clean.

20190518, 17:29  #27  
"Tilman Neumann"
Jan 2016
Germany
731_{8} Posts 
Quote:
Quote:
Quote:
Quote:
Otherwise you will get many duplicate relations, and those will lead to many fails in the linear algebra step. In my software I do get some duplicate relations and more final factor tests than theoretically required, but checking for duplicate relations would be worse performancewise. Finally: It took me 3 month to implement the first working version. You should not give up short before the goalline ;) 

20190519, 02:37  #28  
May 2019
2^{3}×3 Posts 
Quote:
Quote:
For the 40digit number I mentioned, it is sieving and picking up relations much more quickly (due to the reduced sieve size). It is also finding a factor much more quickly (on the first try, in fact), which would seem to indicate that this new method of generating is an effective way of reducing duplicate relations. For this number, it's still not as fast as MPQS but significantly faster than before. However, for the 50digit number, the generation of slows to a crawl (basically a halt) after enough qcandidates are removed. I started out with 250 qcandidates and at some point after 150200 polynomials, when between 50100 candidates are remaining, it takes far too long to find a suitable set of s. Would a more sophisticated method to generate maintain a constant time cost no matter which polynomial it is (i.e., the first or the th)? By the way, I also tried generating using something like the CarrierWagstaff method (to the extent that I could understand it):
This completely backfired and could not even find a single , ever. I think the qbase product was always too high. Last fiddled with by tabidots on 20190519 at 02:40 

20190519, 17:23  #29  
"Tilman Neumann"
Jan 2016
Germany
11×43 Posts 
Quote:
Quote:
You might try to port my AParamGenerator01 class. It does not need a particular range of primes reserved for the aparameter computations. The backdraw is that you have to filter the prime base after each aparameter computation. The latter is pretty quick though. Last fiddled with by Till on 20190519 at 17:25 Reason: about small N 

20190520, 07:57  #30  
May 2019
18_{16} Posts 
Quote:
Are you removing all the used s from the candidates after generating each ? When accumulating s, how do you guarantee that you have not surpassed too early? If `randomOffset` happens to be positive on every iteration, then that would happen, right? Last fiddled with by tabidots on 20190520 at 07:57 

20190520, 14:16  #31  
"Tilman Neumann"
Jan 2016
Germany
111011001_{2} Posts 
Quote:
You analyzed 13 correctly. About 4: It is not a binary search, but a stepbystep search around the theoretically best qvalue for the first free q. To find the first free q, I keep a list of those q already in use (instead of removing used q's from an "all qlist"). This procedure helps to give enough randomness to the final result. The deterministic computation of the last q makes sure that the final avalue is very near the theortically best avalue. 

20190521, 00:22  #32 
Tribal Bullet
Oct 2004
3×1,181 Posts 
Another effective strategy for nottoolarge problems is to precompute a list of bitfields. The first bitfield has the bottom k bits set (k the number of primes in A) and successive values also have k bits set but with loworder bits clear and higherorder bits set, with each bitfield chosen to have at least two bits different from all the others. For j even, bit j set refers to a factor base prime j/2 above the optimal q value and j odd similarly below the optimal q value.
When k = 3,4,5,6 it doesn't take a large bitfield to generate a lot of different A values that are nearly guaranteed to avoid duplicate relations 
20190521, 06:12  #33  
May 2019
2^{3}×3 Posts 
I found a library with a weightedsample function that can take random samples and an optional weighting function, so I experimented with using a normal distribution as the function, with , and using all factorbase primes > 2 as the candidate pool. (Removed 2 as it causes a NullPointerException after some number of polynomials, probably in computing the modular square roots or something.)
For the last , it chooses the nearest prime in the factor base in a manner similar to yours. (As is preferred in Clojure, I am trying very hard to do this without fiddling with array indexes, so that the code be can be written in a declarative rather than imperative style.) It generates values that pick up smooths, so I guess it "works"—but only up to a point. At some point, enough polynomials are generated that there are no more "free qs" and my qcollection consists of just one , slowing the program to a crawl. What did I do wrong, that I run out of candidates? (This didn't happen before since I was only removing 1 or 2 items from the candidate pool after each polynomial, not 5 or 6.) Quote:
Code:
qIndexSet.add(qIndex); Last fiddled with by tabidots on 20190521 at 06:17 

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 