mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-05-21, 10:13   #34
tabidots
 
May 2019

23×3 Posts
Default

I am trying different sieve sizes, different methods of finding A, different numbers of used-q's to remove from the q-pool after each polynomial (1, 2, or all), different log-thresholds... But ultimately I don't think I'm gaining any additional understanding of what I am supposed to do.

I have managed to get roughly equal performance to MPQS (slightly slower) on an easy 26-digit number. It finds a factor on the first try a vast majority of the time, and when that happens, it takes "only" 1.5x as long as MPQS, compared to 5x before. This happens after ~12 As.

But I am running out of primes on the 40-digit number, even if I only take one "used-q" away on every iteration, because it picks up smooths so much more slowly.

TL;DR: It seems that when I try to change the A-generator to generate better As, I run out of q-candidates before enough smooths are generated, while if I set the parameters so that enough smooths can be generated (even if slowly), the linear algebra step never terminates due to bad quality smooths.

There seem to be a few interrelated issues at play here, in determining the speed (and success!) of the whole program:

1. Accuracy of A (i.e., proximity of generated A to ideal A)

My original method (Method #1) actually achieved this quite well (though it did get progressively slower). Still, it did not accumulate smooths quickly enough.

2. Speed of generating A.

Tilman's method (Method #2) works faster than Method #1 but requires setting the number of qs in advance. It's also fairly complicated.

I managed to achieve similar speed at the expense of a little accuracy by tweaking my Monte Carlo method so that once the product of the randomly-accumulated qs passes the tipping point, it backtracks (popping the last q) and finds the best-fitting free q. (Method #3)

Of course, eventually the program reaches a point where there aren't many free qs left, so it can't produce good As anymore.

While the accuracy of Method #3 fluctuates a little more than Method #2, the inaccuracy of Method #2 spirals out of control as the number (variety) of free q's decreases.

In any case, changing the methods of generating A did not cause a noticeable improvement in the speed of accumulating smooths (i.e., smooths per A).

3. Size of qs.

Not sure what effect this has, other than causing SIQS to run out of q-candidates sooner when using only primes between 400 and 4000, versus all odd primes.

4. Log threshold.

Lowering this increases smooths per A, as you would expect, but increases the time spent checking possible smooths much, much more, so it's not worth it.

5. Distinctiveness of q-sets.

q-sets must be distinct at least to some extent, because duplicate relations will cause problems for the linear algebra step. However, it seems that this is not the only "bad influence", because even when I ensure that every set of qs is completely distinct, it occasionally does not find a factor on the first try (first try = as soon as count(FB) + 1 smooths are accumulated).

I just had one run that actually took 22s compared to the average of ~0.5s to factor the 26-digit number; 11 more polynomials were required, and it did the LA procedure after each of those, which is a major time cost if none of the "winning matrix subsets" produce a factor.

So, taking all of the above into account... what actually determines how many good smooths each polynomial will pick up?

Last fiddled with by tabidots on 2019-05-21 at 10:31
tabidots is offline   Reply With Quote
Old 2019-05-21, 14:16   #35
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by tabidots View Post
Of course, eventually the program reaches a point where there aren't many free qs left, so it can't produce good As anymore.
This should never happen with large enough inputs. If you have a pool of candidate factors say from 1000 to 4000 (for inputs that have factor bases with primes >= 4000), then you are choosing 6 out of 200 or so candidates. The number of combinations is practically infinite. The backtracking method seems like a good one. If everything but the best-fit prime are chosen randomly you should never run out of unique candidate A's.

This is pretty close to what I do... although it does require a large enough pool. My SIQS doesn't work at all below about 35 digits for this reason.

Quote:
Originally Posted by tabidots View Post

So, taking all of the above into account... what actually determines how many good smooths each polynomial will pick up?
Fundamentally it is the size of the Q(x) = (ax + b)^2 - N that you try to factor via sieving. MPQS is faster than QS because changing a,b prevents Q(x) from getting too large as x continues to increase. SIQS is faster than MPQS because more quickly changing a,b allows you to further decrease the range of x and thus the average size of Q(x) over that range.

But, as you've observed, a number of things have to be tuned correctly first.

Quote:
Originally Posted by tabidots View Post
it occasionally does not find a factor on the first try (first try = as soon as count(FB) + 1 smooths are accumulated).
There is no guarantee that it will... there is only a 50% chance that each GCD(X-Y,N) will yield a proper factor of N.
bsquared is offline   Reply With Quote
Old 2019-05-21, 14:24   #36
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·32·7·47 Posts
Default

For n factors of A, my code randomly selects two sets of approximately number of factors that add upto n-1 factors. The last prime is selected in order to make A the optimum size. The two sets are checked(by multiplying the set together and checking a hash set) whether they are unique. If not they would be regenerated. This seems to work for me. I don't get many duplicate relations now that I have fixed the slight overlap bug.
henryzz is offline   Reply With Quote
Old 2019-05-21, 14:28   #37
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by bsquared View Post
This should never happen with large enough inputs. If you have a pool of candidate factors say from 1000 to 4000 (for inputs that have factor bases with primes >= 4000), then you are choosing 6 out of 200 or so candidates. The number of combinations is practically infinite. The backtracking method seems like a good one. If everything but the best-fit prime are chosen randomly you should never run out of unique candidate A's.
Maybe also worth mentioning... don't try to overoptimize choice of A (i.e., closeness to a target A). Any candidate A with the same number of bits as the target A should be good enough to yield relations. YAFU tries to dial things in a bit closer, striving for lg2(target_A - candidateA) < 0.9 * lg2(target_A) (i.e., matching the first 10% or so of bits of the target). But this quickly runs into a wall. Trying to match the first 30% of bits of target A causes a 20x slowdown of the overall factorization!
bsquared is offline   Reply With Quote
Old 2019-05-21, 14:33   #38
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

7318 Posts
Default

Quote:
Originally Posted by jasonp View Post
Another effective strategy for not-too-large 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 low-order bits clear and higher-order 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
That will work but not very fast, because the resulting a-values may deviate a lot from the theoretically best a-value.
Is that why you wrote "for not-too-large problems" ?


Quote:
Originally Posted by tabidots View Post
I found a library with a weighted-sample function that can take k random samples and an optional weighting function, so I experimented with using a normal distribution as the function, with \mu = \hat q = \sqrt[s]{n}, \sigma = 0.3\hat q, and using all factor-base 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 q, 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 a-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 q-collection consists of just one q, slowing the program to a crawl. What did I do wrong, that I run out of q 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.)
Try a bigger sigma. I also use a normal distribution and found that sigma=1 works well, something like 0,75 is a bit faster, but somewhere around 0.55 it gets unstable.

Quote:
Originally Posted by tabidots View Post
Effectively though, you are still trying to ensure that once a q is used, it is never used again, right? As indicated by the presence of

Code:
qIndexSet.add(qIndex);
in each iteration of the loop and after determining the last q.
Yes of course.

Quote:
Originally Posted by tabidots View Post
Tilman's method (Method #2) works faster than Method #1 but requires setting the number of qs in advance. It's also fairly complicated.
It does not require to set the wanted number of qs, it _allows_ it. This is just an option for testing. If you pass "null", then the optimal value I derived from my tests will be computed automatically.

Admittedly the algorithm is not very simple. This reflects the importance of that part and that I invested a considerable time into it ;-)
Till is offline   Reply With Quote
Old 2019-05-21, 14:41   #39
tabidots
 
May 2019

23·3 Posts
Default

All good info, thanks :)

I feel like in some ways Contini's thesis is a bit of a cruel joke, in that it is rather detailed about the whole algorithm except for the generation of A, which is such a crucial part of a successful implementation—in the same way that math textbooks glibly leave the most important details "as an exercise to the reader," haha.

Quote:
Originally Posted by bsquared View Post
This should never happen with large enough inputs. If you have a pool of candidate factors say from 1000 to 4000 (for inputs that have factor bases with primes >= 4000), then you are choosing 6 out of 200 or so candidates. The number of combinations is practically infinite.

The backtracking method seems like a good one. If everything but the best-fit prime are chosen randomly you should never run out of unique candidate A's.
Good to know at least my approach is on the right track :)

Well, while the number of combinations of qs IS practically infinite, it is also important to keep the sets of qs distinct, in order to reduce duplicate relations, isn't it? So I am removing all the used-qs after every polynomial so that every a is made of completely distinct factors from all others. (If I change this to removing one used-q, then every a should be distinct from all others by at least factor, etc.)

Quote:
Originally Posted by bsquared View Post
Maybe also worth mentioning... don't try to overoptimize choice of A (i.e., closeness to a target A). Any candidate A with the same number of bits as the target A should be good enough to yield relations.
Ah... I was actually thinking that more accurate meant more smooths, so I was trying to get the generated a values to within plus-or-minus 1% of the target! My methods #2 and #3 don't actually have a way to specify the degree of precision, but my original method does, so I will try to use bit size rather than error margin as the criteria and see what happens.
tabidots is offline   Reply With Quote
Old 2019-05-21, 14:54   #40
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

11×43 Posts
Default

Quote:
Originally Posted by tabidots View Post
So I am removing all the used-qs after every polynomial so that every a is made of completely distinct factors from all others.

This is your bug / the reason why you are running out off "a"s too quickly.
All you want is to make sure that you get "quite different" a's. If they share e.g. 4 out of 8 q's then that is no problem at all.
Till is offline   Reply With Quote
Old 2019-05-21, 15:02   #41
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by tabidots View Post
All good info, thanks :)

I feel like in some ways Contini's thesis is a bit of a cruel joke, in that it is rather detailed about the whole algorithm except for the generation of A, which is such a crucial part of a successful implementation—in the same way that math textbooks glibly leave the most important details "as an exercise to the reader," haha.
Yes, or the dreaded "it's obvious that..."

Quote:
Originally Posted by tabidots View Post
Well, while the number of combinations of qs IS practically infinite, it is also important to keep the sets of qs distinct, in order to reduce duplicate relations, isn't it? So I am removing all the used-qs after every polynomial so that every a is made of completely distinct factors from all others. (If I change this to removing one used-q, then every a should be distinct from all others by at least factor, etc.)
This is too restrictive. It is ok to reuse some q's. Contini recommends that at least 2 q's be different from a candidate A and all other A's. For a while I checked this, but now I just make sure that each A is unique. In practice, the randomness of the choice of q's over a wide pool of candidates seems to result in enough variability of A and I almost never observe duplicate relations.

Quote:
Originally Posted by tabidots View Post
Ah... I was actually thinking that more accurate meant more smooths, so I was trying to get the generated a values to within plus-or-minus 1% of the target! My methods #2 and #3 don't actually have a way to specify the degree of precision, but my original method does, so I will try to use bit size rather than error margin as the criteria and see what happens.
Here are some examples from the 50 digit test case. You can see that some generated A's are terrible compared to others, but still generate relations.

Code:
0 rels found: 0 full + 0 from 0 partial
target A: 979810739388948469688, generated A: 981164448583280585779, difference in bits: 61
19 rels found: 19 full + 0 from 93 partial
target A: 979810739388948469688, generated A: 787409267794090315519, difference in bits: 68
31 rels found: 31 full + 0 from 147 partial
target A: 979810739388948469688, generated A: 981833090551355617507, difference in bits: 61
51 rels found: 51 full + 0 from 265 partial
target A: 979810739388948469688, generated A: 980132099527861925039, difference in bits: 59
61 rels found: 60 full + 1 from 366 partial
target A: 979810739388948469688, generated A: 974488335157786904569, difference in bits: 63
77 rels found: 76 full + 1 from 480 partial
target A: 979810739388948469688, generated A: 981584000823620726969, difference in bits: 61
90 rels found: 89 full + 1 from 577 partial
target A: 979810739388948469688, generated A: 767831042643641288209, difference in bits: 68
97 rels found: 94 full + 3 from 619 partial
target A: 979810739388948469688, generated A: 977380559589959176853, difference in bits: 62
106 rels found: 101 full + 5 from 714 partial
target A: 979810739388948469688, generated A: 979519609163111612279, difference in bits: 59
114 rels found: 107 full + 7 from 777 partial
target A: 979810739388948469688, generated A: 756160297662920819309, difference in bits: 68
119 rels found: 112 full + 7 from 834 partial
target A: 979810739388948469688, generated A: 700618507243745840251, difference in bits: 68
129 rels found: 120 full + 9 from 882 partial
target A: 979810739388948469688, generated A: 916160591158265796887, difference in bits: 66
138 rels found: 129 full + 9 from 942 partial
target A: 979810739388948469688, generated A: 980816366451859715321, difference in bits: 60
155 rels found: 141 full + 14 from 997 partial, (18348.92 rels/sec)
bsquared is offline   Reply With Quote
Old 2019-05-21, 16:45   #42
tabidots
 
May 2019

1816 Posts
Default

Quote:
Originally Posted by bsquared View Post
Here are some examples from the 50 digit test case. You can see that some generated A's are terrible compared to others, but still generate relations.
Wow, your SIQS finds enough relations to find a factor after just 14 polynomials? After 14 polynomials, I'm still in the single digits for that 50-digit number!

For now, I have changed the A-generation so that A only matches bit size with the goal-A (\frac{\sqrt{2N}}{M}) and each set of qs is completely distinct only with the previous set of qs, so no qs are removed permanently.

Sieve size is chosen arbitrarily. Factor base is determined based on an upper bound 5 (\log_{10}(N))^2.

Code:
Factoring 4493699349619351139582065363011367885289...
Sieve size:  12000
Factor base size:  516
Factor base bound: 7861.645024915483
Max prime:  7853
Goal A (rounded):  7900157654562055
Log threshold: 14.60970050153134

Current smooths: 0/516 (0 primes used)
qs: [857 727 1289 2633 2357]
A: 4984006404977851 Accuracy: 0.6308742968059337

Current smooths: 1/516 (99 primes used)
qs: [1867 1237 461 2689 2267]
A: 6490187823840697 Accuracy: 0.8215263679064491

Current smooths: 2/516 (166 primes used)
qs: [2297 1009 1163 2521 929]
A: 6312776822141291 Accuracy: 0.7990697272346066

Current smooths: 3/516 (212 primes used)
qs: [3343 619 857 1303 3709]
A: 8570557966269263 Accuracy: 1.084859105478746

Current smooths: 5/516 (247 primes used)
qs: [1741 1367 563 1489 3023]
A: 6031266592470767 Accuracy: 0.7634362320589803

Current smooths: 5/516 (291 primes used)
qs: [1607 863 2411 1097 1571]
A: 5762443702375937 Accuracy: 0.7294086971857244

Current smooths: 5/516 (317 primes used)
qs: [811 1489 1487 2129 2137]
A: 8169711193068829 Accuracy: 1.034120020168346

Current smooths: 5/516 (331 primes used)
qs: [2957 739 2621 3343 433]
A: 8290620898562677 Accuracy: 1.049424740755033

Current smooths: 5/516 (346 primes used)
qs: [1873 991 829 1223 3617]
A: 6806767682226277 Accuracy: 0.8615989680023176

Current smooths: 5/516 (367 primes used)
qs: [433 2777 2621 2819 971]
A: 8626708093424389 Accuracy: 1.091966574672441

Current smooths: 5/516 (381 primes used)
qs: [1117 499 1213 3037 2647]
A: 5435171507140681 Accuracy: 0.6879826637386238

Current smooths: 5/516 (387 primes used)
qs: [2003 1163 2999 2621 449]
A: 8221489220932619 Accuracy: 1.040674070116184

Current smooths: 6/516 (397 primes used)
qs: [499 2521 2411 1289 1823]
A: 7127056270082543 Accuracy: 0.9021410181563815

Current smooths: 6/516 (411 primes used)
qs: [853 2687 3719 547 1613]
A: 7520809178288699 Accuracy: 0.951982163792099
tabidots is offline   Reply With Quote
Old 2019-05-21, 17:18   #43
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

Quote:
Originally Posted by tabidots View Post
Wow, your SIQS finds enough relations to find a factor after just 14 polynomials? After 14 polynomials, I'm still in the single digits for that 50-digit number!
No, it needs ~60 A polys but I didn't think anyone cared to see them all :)

Your factor base size, sieve size, and A polys all look pretty good here... there should be abundant smooths to find. I find them at a rate of about 16 full relations per A or 134 partial relations per A for a similar set of parameters (FB size 672, FB max prime 10631, sieve size 32768). So the problem would appear to be somewhere else.

For the relations you do find, can you print a couple of them? Maybe something will reveal itself like maybe forgetting to trial divide by small primes that were skipped (I remember doing that in one of my first experimental versions).

Another debug tactic: for a given A,B and sieve block, go through and compute Q(x) for every sieve location and factor all of them completely prior to sieving (by simple trial division with all primes up to sqrt(Q(x)), for example). Then you will know which locations should be found by the sieve process. If a location is not found that should be during the subsequent sieve, you will have a specific example with which to work more closely. Are the appropriate primes hitting that location during the sieve? if not, why not? etc.
bsquared is offline   Reply With Quote
Old 2019-05-21, 23:49   #44
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3×1,181 Posts
Default

Quote:
Originally Posted by Till View Post
That will work but not very fast, because the resulting a-values may deviate a lot from the theoretically best a-value.
Is that why you wrote "for not-too-large problems" ?
For not too large problems the size of the table is small, and my experience is that when the sieving is tuned each polynomial finds lots of relations even if the A value is not very close to optimal size.
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
SIQS problems henryzz Factoring 2 2013-08-26 23:02
SIQS Problem patrickkonsor Factoring 3 2008-10-20 12:03
HELP! Online diagnostics lythanhnguyen Hardware 3 2007-09-11 06:19
Memory Diagnostics under XP? R.D. Silverman Hardware 3 2006-11-17 16:06

All times are UTC. The time now is 09:12.


Tue Oct 26 09:12:50 UTC 2021 up 95 days, 3:41, 0 users, load averages: 2.12, 2.09, 2.10

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.