Gratuitous factors thread - Page 43

petrw1 · 2019-01-12, 15:03

Quote:

Originally Posted by LaurV

not really twins (difference of 10), and generally, you can't factor a prime...

I posted in a hurry and then I suspected someone would get me on the details/semantics …

Are they not twins if there are NO primes between them? Or is there a better term?
Ok I googled; not twins; or cousins; or even sexy, but still consecutive primes. I stand corrected.

And I know that everyone (you too) knew I meant I factored the Mersenne prime with these exponents.
But we can have fun keeping each other on their toes.

Nooks · 2019-01-14, 00:18

A factorization of a 172-digit composite into 88-digit and 84-digit primes with CADO-NFS's development version (git revision 0dec81292) and the default params.c170 file:

Code:

3016383496950006147092688200424946917422706718391310384294721528855721834292309567932262756723784125877970431370173942976562831621594395308639675419510349700482607657451341
== 446312748645718146132684289764373070973541797549254695585526735493360431216546061841
* 6758452466578325810330347608534512938095716148720844026944541733955827767173119787909501

Code:

n: 3016383496950006147092688200424946917422706718391310384294721528855721834292309567932262756723784125877970431370173942976562831621594395308639675419510349700482607657451341
skew: 5687366.741
c0: 1844365051828556051246292858200517299056
c1: -652680455268348606492829307490528
c2: -42979525126081196796415117
c3: -747412658435266339995
c4: -16124985610032
c5: 2706480
Y0: -1348430098615952463172584497847510
Y1: 242062762813618602089
# MurphyE (Bf=2.147e+09,Bg=1.074e+09,area=2.631e+15) = 2.96e-08
# found by revision 0dec81292
# f(x) = 2706480*x^5-16124985610032*x^4-747412658435266339995*x^3-42979525126081196796415117*x^2-652680455268348606492829307490528*x+1844365051828556051246292858200517299056
# g(x) = 242062762813618602089*x-1348430098615952463172584497847510

Yes, this is another factor of (34*10^279 - 61)/9, but I decided to trust Makoto Kamada's assessment that it would factor faster with GNFS than SNFS.

Looks like polynomial selection ran for 6.5h, sieving took 5 days 16 hours (both jobs distributed across 6 machines) and linear algebra took 7 days 13 hours, though these times are estimates only.

Along with a 230-digit SNFS job from January 3rd, all in all a good start to the year.

VBCurtis · 2019-01-14, 06:20

Nooks-
If you are able to post some timings, I would appreciate having them as a baseline for when I develop params for 170+ numbers.
I can get the input params from the Git distribution; if you have them I'd like the following from the last page or two of the screen display (and thus, perhaps, the log file, though I haven't looked there):
Total sieving time
bwc time
total CPU time (wall clock not relevant since you used multiple machines).
If you could scroll up to just above the start of the matrix phase, the total matrix weight would be nice too, but that's secondary to the timings.

Nooks · 2019-02-01, 03:08

The final 191-digit composite factor of $(34*10^{255}-61)/9$ via SNFS:

Code:

236629558781563913152694288465588385072932963576605354172203938573603707688\
657537351091535752598011220253440476681720689237296299832984394194906581349\
98810605512544414399653796835562442062749
== 758248354419233258221885990957066295939092170798035281629413131115956168\
07051026803657302059
* 3120739496530870602238825207916337507864541192949895693245364011021398842\
82412308031192400107693911

Code:

n: 23662955878156391315269428846558838507293296357660535417220393857360370768865753735109153575259801122025344047668172068923729629983298439419490658134998810605512544414399653796835562442062749
skew: 0.35
c0: -61
c6: 34000
Y0: -1000000000000000000000000000000000000000000
Y1: 1
# f(x) = 34000*x^6-61
# g(x) = x-1000000000000000000000000000000000000000000

That's a p95 and a p99! No hope for ECM there, but the supplied polynomial took care of it ably in just over two weeks:

Code:

Generate Factor Base: Total cpu/real time for makefb: 99.59/21.3723
Generate Free Relations: Total cpu/real time for freerel: 1360.09/193.008
Lattice Sieving: Total time: 3.35592e+07s
Filtering - Duplicate Removal, splitting pass: Total cpu/real time for dup1: 1046.05/799.656
Filtering - Duplicate Removal, removal pass: Total cpu/real time for dup2: 5185.82/1825.88
Filtering - Singleton removal: Total cpu/real time for purge: 4031.2/1504.99
Filtering - Merging: Total cpu/real time for merge: 9195.7/8388.62
Filtering - Merging: Total cpu/real time for replay: 509.53/424.943
Linear Algebra: Total cpu/real time for bwc: 1.30761e+07/337028
Quadratic Characters: Total cpu/real time for characters: 513.59/126.766
Square Root: Total cpu/real time for sqrt: 18426/2744.89
Complete Factorization: Total cpu/elapsed time for entire factorization: 6.74113e+07/1.27886e+06

DukeBG · 2019-03-07, 16:45

My first attempt at doing a (S)NFS factorization on my own finally complete.
The number was C157 from M2856, i.e. cofactor of 2^1428+1

it split into

Quote:

p68 factor: 35670942157302652690824989897487529464738030858042402149021099984593
p89 factor: 37767852130457868731562073128156176253423576887465596274025192402227147257043900241563521

(this is above cunningham project range, where I "work")
(out of the cofactors of mersenne numbers with composite exponent – i'm excluding the wagstaff numbers too – at the moment there were only 22 currently 200dd and below, this was the smallest)
(next one I'll be working on will be C159 from the lower aurifellian "half" of M5340, i.e. 2,2670L in cunningham project notation. it used to be C200 before I found a P41 during a t45 ECM. I've since ran ECM to t50 and will run more before starting NFS)

VBCurtis · 2019-03-07, 17:52

Quote:

Originally Posted by DukeBG

(next one I'll be working on will be C159 from the lower aurifellian "half" of M5340, i.e. 2,2670L in cunningham project notation. it used to be C200 before I found a P41 during a t45 ECM. I've since ran ECM to t50 and will run more before starting NFS)

For a C159, T50 is sufficient for ECM. An old rule of thumb was to do ECM to 0.33*{GNFS input digits}, but over the last few years two things happened: GNFS got a bit faster (either CADO or better parameters for C150s and C160s in e.g. YAFU), and user fivemack built a Bayesian ECM tool that showed (I won't say "proved" because I didn't pay close enough attention to whether it was rigorous or heuristic; I think it was heuristic) we had been doing too much ECM. I use 0.31* {input digits}, which in your case is 49.3 digits of ECM, just a touch under t50.

Another way to guesstimate ECM depth is to use 0.33*{input digits}, and then do half that much ECM.
It's not a massive waste for you to do 75% as much, or 50% extra, of "optimal" ECM, but don't feel like you *need* to do more ECM before you jump in to GNFS.

DukeBG · 2019-03-15, 06:42

Quote:

Originally Posted by DukeBG

(next one I'll be working on will be C159 from the lower aurifellian "half" of M5340, i.e. 2,2670L in cunningham project notation.)

C159 split into

Code:

p77 factor: 14395422614070252889320736657833207061788526074290028178132689141296169594901
p83 factor: 49230132958996393737968357088119278041863452859497085931935198555333741322274461901

There's a next one C161 which I guess I'll also be able to do in slightly more than a week, but i'll likely take a break for other work first. Also, I'm not sure if I should use this thread for these results.

fivemack · 2019-04-14, 08:39

Code:

Sat Apr 13 23:26:19 2019  p63 factor: 296487969525296276850921981749786845648115727996781154088552709
Sat Apr 13 23:26:19 2019  p136 factor: 2875934486229125150363886610871286062228526402357438883980261213555353869456660982295169078268290455092395769879076574162437017394717449

GNFS, log N = 197.93

Linear algebra was 436.4 clock-hours on 14 cores i9/7940X; sieving was 142 calendar days on a variety of machines (327960 thread-hours, average 96 threads)

Polynomial selection was about 13 days on 48 cores (c5=100M..148M, stage1 norm 2e30, filtered with stage2 norm 3e27) ; polynomial used was

Code:

n: 852679976309849462561536948832252846150022423314081294539696739447185168605454946622214267597669582414001048054414801767580861775753868718426635210602520095957947143580737129768159250338498398519341
# size 1.520e-19, alpha -8.037, combined = 5.249e-15 rroots = 5
skew: 87449658.66
c0: -19173795040547917922319576642461732013068609000
c1: 11624482281468240523430055237992563747370
c2: -151621758548975810978340099738421
c3: -13148951379326142412839968
c4: 15717746636680866
c5: 145180728
Y0: -89903255613260185328110621485495452493
Y1: 597297877329514173839
lpbr: 33
lpba: 33
mfbr: 66
mfba: 96
alambda: 3.4
rlambda: 2.4
alim: 268000000
rlim: 268000000

Sieved 85M-330M with 16e to get 808562346 relations, 631972026 unique. Filtered at density 130 (140 didn't work);

Code:

Tue Mar 26 14:39:06 2019  matrix is 39891210 x 39891388 (20304.8 MB) with weight 6098284592 (152.87/col)
Tue Mar 26 14:39:06 2019  sparse part has weight 4844082745 (121.43/col)
Tue Mar 26 14:48:05 2019  filtering completed in 2 passes
Tue Mar 26 14:48:14 2019  matrix is 39890195 x 39890373 (20304.7 MB) with weight 6098240356 (152.87/col)
Tue Mar 26 14:48:14 2019  sparse part has weight 4844072509 (121.43/col)
Tue Mar 26 14:50:33 2019  matrix starts at (0, 0)
Tue Mar 26 14:50:39 2019  matrix is 39890195 x 39890373 (20304.7 MB) with weight 6098240356 (152.87/col)
Tue Mar 26 14:50:39 2019  sparse part has weight 4844072509 (121.43/col)
Tue Mar 26 14:50:39 2019  saving the first 240 matrix rows for later
Tue Mar 26 14:50:49 2019  matrix includes 256 packed rows
Tue Mar 26 14:51:02 2019  matrix is 39889955 x 39890373 (18437.2 MB) with weight 4450167471 (111.56/col)
Tue Mar 26 14:51:02 2019  sparse part has weight 4194944839 (105.16/col)

Log attached

DukeBG · 2019-04-15, 17:10

Quote:

Originally Posted by DukeBG

There's a next one C161 which I guess I'll also be able to do in slightly more than a week, but i'll likely take a break for other work first. Also, I'm not sure if I should use this thread for these results.

Instead of C161 I found a P43 in a C196 making it C154. Finished GNFS on that today (about 3+ days of sieving and 4 hours of LA, regretting spending 1+ days on poly select). 2^3570+1 is now fully factored.

GP2 · 2019-04-15, 17:19

Quote:

Originally Posted by DukeBG

2^3570+1 is now fully factored.

I see a C283 on FactorDB ?

DukeBG · 2019-04-15, 17:36

Quote:

Originally Posted by GP2

I see a C283 on FactorDB ?

Your link is to 2^3750+1

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Gratuitous OPN factors	wblipp	Factoring	463	2019-05-30 07:19
Ungracious Factors Thread	FactorEyes	Factoring	2	2011-04-09 05:45
Missing factors at the 'Known Factors' page	MatWur-S530113	PrimeNet	11	2009-01-21 19:08
JasonG's gratuitous C++ thread	jasong	Programming	16	2006-11-07 01:03
Gratuitous hardware-related banana thread	GP2	Hardware	7	2003-11-24 06:13

2019-01-14, 06:20	#465
VBCurtis "Curtis" Feb 2005 Riverside, CA 4629₁₀ Posts	Nooks- If you are able to post some timings, I would appreciate having them as a baseline for when I develop params for 170+ numbers. I can get the input params from the Git distribution; if you have them I'd like the following from the last page or two of the screen display (and thus, perhaps, the log file, though I haven't looked there): Total sieving time bwc time total CPU time (wall clock not relevant since you used multiple machines). If you could scroll up to just above the start of the matrix phase, the total matrix weight would be nice too, but that's secondary to the timings.