mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-10-18, 22:12   #56
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

22×33×5×11 Posts
Default

Switching degree may change the best side to sieve on as well. Increasing the degree reduces the size of the norms on the rational side and increases those on the algebraic. For a large deg5 job sieve on the rational size. A small deg6 job will want sieving on the algebraic.

Parameters can also be biased towards one side or other when the size of the norms is skewed. A common thing you will see is three large primes on one side.



When is the crossover to running -A 28 rather than -I 14 (equivalent to -A 27)? It sounds like the duplicate rates are getting up there.
henryzz is offline   Reply With Quote
Old 2021-10-18, 22:38   #57
charybdis
 
charybdis's Avatar
 
Apr 2020

22416 Posts
Default

Quote:
Originally Posted by henryzz View Post
When is the crossover to running -A 28 rather than -I 14 (equivalent to -A 27)? It sounds like the duplicate rates are getting up there.
For GNFS it appears to be in the high 160s, so there's probably a way to go. CADO will always give higher duplication rates than ggnfs because it sieves below the FB bound.
charybdis is offline   Reply With Quote
Old 2021-10-19, 00:05   #58
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

2·43·59 Posts
Default

I reckon deg 6 and 5 will be competitive around 2^700. That is, from something like 2^680 to 2^720 which one is faster depends on the individual polynomials.

On ggnfs, I found 15e faster than 14e starting around 2^800; so I imagine A=28 should be test-sieved starting around 2^760.

bur- In general, if sieving time seems longer than you expect for the size of job, you should do some of:
1. Add 50% to each lim
2. add 1 to each mfb.
3. if #2 helped but not that much, add another 1 to mfb and maybe also add 1 to lpb on one side. If you add 1 to an LPB, expect to need 30% more relations.

I found that as jobs get bigger, mfb's closer to 2* lpb run faster, and increasing mfb on the non-sieving side seems to help speed more. Before I go up to try LPB=32 (around GNFS-165 or SNFS-230), I think I'd increase the MFB's to 2 * LPB -1.

at GNFS-145, I have LPB of 30/31 and MFB of 56/60, with 56/59 nearly exactly the same speed. Lambdas are 1.83 and 1.91. SNFS optimizing might use 57/60 or 57/59, or 31/31 with mfb of 59 or 60 on both sides. Also, it seems that using lambda is less effective on medium sized jobs than small jobs- you can try deleting lambda settings entirely and see if your job gets faster.

At GNFS-150, I only change lim's but not mfb/lpb settings so far. I haven't yet run a job whose timing matches my best-timing curve-fit, so I continue to experiment. lim's around 15M for GNFS-145 and ~20-25M for GNFS-150 likely make sense, but you might try going bigger on your own jobs to see what happens.
VBCurtis is offline   Reply With Quote
Old 2021-10-19, 10:37   #59
charybdis
 
charybdis's Avatar
 
Apr 2020

10448 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
bur- In general, if sieving time seems longer than you expect for the size of job, you should do some of:
1. Add 50% to each lim
2. add 1 to each mfb.
3. if #2 helped but not that much, add another 1 to mfb and maybe also add 1 to lpb on one side. If you add 1 to an LPB, expect to need 30% more relations.
Worth noting here that adding 1 to each mfb may do basically nothing if the lambdas are too small. Maybe add 0.05 to each lambda at the same time.
charybdis is offline   Reply With Quote
Old 2021-10-19, 12:48   #60
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

594010 Posts
Default

What is the difference between limiting cofactorization using lambda and mfb? Are these bounds applied at different stages? It looks to me like the lambda limits are used when the exact size of the composite cofactor is slightly questionable(before resieving to get the factors?). I don't get why we set lambda as a multiple of lpb and mfb as a bit level though. Wouldn't using the same scale make sense. In bits I would expect lambda to be slightly more than mfb to allow for error in the approximation.
I usually just set mfb and leave lambda to the default. Am I missing much? Is lambda defined the same way in CADO and ggnfs?
henryzz is offline   Reply With Quote
Old 2021-10-19, 13:43   #61
charybdis
 
charybdis's Avatar
 
Apr 2020

54810 Posts
Default

Indeed lambda is applied before the size of the cofactor is known exactly - as you're probably aware, some crude but clever approximations are used for log2 during sieving.

I don't know why lambda is defined as a multiplier rather than just a bit-level. Possibly it's just for historical reasons, but CADO uses a different definition of lambda from ggnfs: CADO's lambda is a multiple of the lpb bound, but ggnfs's lambda is a multiple of the factor base bound, which is rather unhelpful since the factor base bound isn't expressed in bits.

By default, CADO sets lambda to mfb/lpb + 0.3. VBCurtis's experiments appear to show that for smaller numbers it can actually be beneficial to set lambda below mfb/lpb. This has the effect of turning the cutoff from a sharp one into a more gradual one. Quite why this works is beyond me.
charybdis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
A new tool to identify aliquot sequence margins and acquisitions garambois Aliquot Sequences 24 2021-02-25 23:31
Comparison of GNFS/SNFS With Quartic (Why not to use SNFS with a Quartic) EdH EdH 14 2020-04-20 16:21
new candidates for M...46 and M48 cochet Miscellaneous Math 4 2008-10-24 14:33
Please identify! Brian-E Lounge 24 2008-08-01 14:13
Easily identify composites using multiplication Nightgamer360 Miscellaneous Math 9 2007-07-09 17:38

All times are UTC. The time now is 03:35.


Wed Dec 8 03:35:16 UTC 2021 up 137 days, 22:04, 2 users, load averages: 1.25, 1.13, 1.25

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.