Reserved for MF - Sequence 4788 - Page 72

FactorEyes · 2010-02-10, 23:01

Quote:

Originally Posted by Batalov

No, it doesn't. "52" only controls the internal mechanics of the siever. It should be chosen to optimize the speed.

I believe that mfbr/a (thanks to jrk for the proper way to specify these two as one) is the largest remaining unfactored number (or norm) which the siever will bother to bust into large primes: above this size, it chucks that (a,b) combination.

Is this correct?

jrk · 2010-02-10, 23:57

Quote:

Originally Posted by FactorEyes

I believe that mfbr/a (thanks to jrk for the proper way to specify these two as one) is the largest remaining unfactored number (or norm) which the siever will bother to bust into large primes: above this size, it chucks that (a,b) combination.

Is this correct?

I see. I think you mean that, the smaller the unfactored part is after removing small primes, the smaller will be the large primes that come out of it. So not as many of them would be needed to build a matrix. If that's the case, though, I don't know what the proper formula is to determine how many needed relations should be deducted because of this. But in this case it must be at least about 7% less for changing mfbr/a from 54 to 52 for it to be any faster.

Quote:

Originally Posted by axn

Yes, but 27,52 requires fewer relations than 27,54 (something like 10%(?) less). So...

Where do you get that 10%?

If anyone wants to sieve the number, please go ahead and use some other parameters. I did not mean to start confusion.

axn · 2010-02-11, 00:32

Quote:

Originally Posted by Batalov

No, it doesn't. "52" only controls the internal mechanics of the siever.

Yeah, it does. With 27/52 you'll get a usable matrix with fewer relations.

Quote:

Originally Posted by jrk

Where do you get that 10%?

Quoting from memory based on past experience (+/-)

FactorEyes · 2010-02-11, 04:13

Quote:

Originally Posted by jrk

I see. I think you mean that, the smaller the unfactored part is after removing small primes, the smaller will be the large primes that come out of it. So not as many of them would be needed to build a matrix.

Actually, I have no idea.

If one drops the mfbr/a values relative to lpbr, then you'll pull fewer large primes, but spend less time fruitlessly factoring large chunks that will yield nothing anyway, and smaller cliques, with more found as a total percentage of relations found, but the relationships among all these are so zany that I really don't know the answer.

I'm just trying to pin down the precise definition of mfbr/a. Intuitively, it seems that a smaller mfbr/a would not make a difference, now that I think about it, but I have been wrong enough times about these things.

It seems to be time for a series of tests on GNFS 100 through GNFS 125 - one would need to actually sieve them to the matrix stage and compare the return.

We could use data for larger GNFS, and SNFS jobs. I might as well do some of this - it could take quite a while. Maybe I'll start with a aliquot sequence in the low 100s, and sieve each composite 3-4 different ways. Ugh.

Quote:

Originally Posted by axn

Yeah, it does. With 27/52 you'll get a usable matrix with fewer relations.

Quoting from memory based on past experience (+/-)

Seems to be little consensus on this stuff: this will be the first experiment I'll try.

Batalov · 2010-02-11, 05:59

It's true that this not clearly black-or-white.

With lower mfbX, one will get an initial matrix with fewer relations, but later by CPU time; such sieving happens to be both slower and more redundant. Run tests to see.

Also, secondary consideration is that for larger projects it is of less importance that an initial matrix may be built with fewer relations; in distributed projects, people systematically and deliberately oversieve.

For this relatively low range, I will be not surprised if an optimal mfbX may be lpbX*2-1. Any volunteers to comprehensively check what is the best mfbX for gnfs-180? Such results will be undoubtedly most welcome.

henryzz · 2010-02-11, 07:33

I did a test a while back with small gnfs numbers. early 90s digit wise I think. having lower mfbX was very helpful for making a factorization faster time wise. The reason being I think was that it got the benefit from some of the larger large primes were not singletons which helped produce the matrix but were gained at very little extra cost of time. As long as relation production is slow enough to not mean the disk slows us then I think that as long as we have the full factorization available then the relation should be saved no matter how many large primes the number already has or the size of the largest large prime. It might not help much but as long as the cost is lower then it would be worth it. These changes dont need extra effort in factoring (a,b) pairs just more outputs.
How easy would it be to allow more large primes to be outputed from gnfs-lasieve?
Would switching to only two large primes for very small factorizations be helpful? I don't think so but it is worth trying.

bsquared · 2010-02-11, 14:58

... Meanwhile, our C128 is getting lonely. I'll do it, using 26/52. Since I can do it pretty fast, maybe I'll play around with complete factorizations using different settings as well, but lets move past this low hurdle first.

bsquared · 2010-02-12, 02:15

The C128 is done:

Code:

prp42 factor: 831368657060398871067580635483867168226159
prp86 factor: 14930977716074183218202849037086987095402611116492933462800195088349992532423708467017

now on a C160

jrk · 2010-02-12, 02:40

Quote:

Originally Posted by bsquared

now on a C160

Code:

Using B1=3000000, B2=5706890290, polynomial Dickson(6), sigma=2809319855
Step 1 took 11575ms
Step 2 took 4886ms
********** Factor found in step 2: 6977898771856757179216213182115242430943227
Found probable prime factor of 43 digits: 6977898771856757179216213182115242430943227
Probable prime cofactor 473028589072800985492970050195364334013736618114591097601498072758055162228629376693218157854131039061545633483665441 has 117 digits

now c123

Batalov · 2010-02-12, 02:44

...a c124 (ready for gnfs)

oops, done. Now a c153.

jrk · 2010-02-12, 03:16

Quote:

Originally Posted by Batalov

...a c124 (ready for gnfs)

~~I will throw a couple hours of poly selection on it. Should get something usable tonight.~~

edit: aborted

2010-02-11, 05:59	#786
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,497 Posts	It's true that this not clearly black-or-white. With lower mfbX, one will get an initial matrix with fewer relations, but later by CPU time; such sieving happens to be both slower and more redundant. Run tests to see. Also, secondary consideration is that for larger projects it is of less importance that an initial matrix may be built with fewer relations; in distributed projects, people systematically and deliberately oversieve. For this relatively low range, I will be not surprised if an optimal mfbX may be lpbX2-1. Any volunteers to comprehensively check what is the best mfbX for gnfs-180? Such results will be undoubtedly most welcome. Last fiddled with by Batalov on 2010-02-11 at 06:07 Reason: a typo and a link*

2010-02-12, 02:15	#789
bsquared "Ben" Feb 2007 DC0₁₆ Posts	The C128 is done: Code: prp42 factor: 831368657060398871067580635483867168226159 prp86 factor: 14930977716074183218202849037086987095402611116492933462800195088349992532423708467017 now on a C160

2010-02-12, 02:44	#791
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9,497 Posts	...a c124 (ready for gnfs) oops, done. Now a c153. Last fiddled with by Batalov on 2010-02-12 at 03:29

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Reserved for MF - Sequence 3366	RichD	Aliquot Sequences	470	2021-04-22 02:17
Reserved for MF - Sequence 3408	RichD	Aliquot Sequences	474	2021-03-07 20:28
Reserved for MF - Sequence 276	kar_bon	Aliquot Sequences	127	2020-12-17 10:05
Assignments are reserved but not showing up	prism019	GPU to 72	6	2020-09-21 22:11
80M to 64 bits ... but not really reserved	petrw1	Lone Mersenne Hunters	82	2010-01-11 01:57

2010-02-11, 07:33	#787
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 5886₁₀ Posts	I did a test a while back with small gnfs numbers. early 90s digit wise I think. having lower mfbX was very helpful for making a factorization faster time wise. The reason being I think was that it got the benefit from some of the larger large primes were not singletons which helped produce the matrix but were gained at very little extra cost of time. As long as relation production is slow enough to not mean the disk slows us then I think that as long as we have the full factorization available then the relation should be saved no matter how many large primes the number already has or the size of the largest large prime. It might not help much but as long as the cost is lower then it would be worth it. These changes dont need extra effort in factoring (a,b) pairs just more outputs. How easy would it be to allow more large primes to be outputed from gnfs-lasieve? Would switching to only two large primes for very small factorizations be helpful? I don't think so but it is worth trying.

2010-02-11, 14:58	#788
bsquared "Ben" Feb 2007 2⁶·5·11 Posts	... Meanwhile, our C128 is getting lonely. I'll do it, using 26/52. Since I can do it pretty fast, maybe I'll play around with complete factorizations using different settings as well, but lets move past this low hurdle first.