mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-01-12, 15:03   #463
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

2×2,213 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
petrw1 is offline   Reply With Quote
Old 2019-01-14, 00:18   #464
Nooks
 
Jul 2018

1910 Posts
Default

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.
Nooks is offline   Reply With Quote
Old 2019-01-14, 06:20   #465
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·191 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2019-02-01, 03:08   #466
Nooks
 
Jul 2018

19 Posts
Default

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
Nooks is offline   Reply With Quote
Old 2019-03-07, 16:45   #467
DukeBG
 
Mar 2018

3·43 Posts
Default

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)
DukeBG is offline   Reply With Quote
Old 2019-03-07, 17:52   #468
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

112916 Posts
Default

Quote:
Originally Posted by DukeBG View Post
(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.
VBCurtis is offline   Reply With Quote
Old 2019-03-15, 06:42   #469
DukeBG
 
Mar 2018

3·43 Posts
Default

Quote:
Originally Posted by DukeBG View Post
(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.
DukeBG is offline   Reply With Quote
Old 2019-04-14, 08:39   #470
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000101100102 Posts
Default L1657 factored in fivemack's shed

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
Attached Files
File Type: log L1657.log (106.8 KB, 30 views)

Last fiddled with by fivemack on 2019-04-14 at 08:40
fivemack is offline   Reply With Quote
Old 2019-04-15, 17:10   #471
DukeBG
 
Mar 2018

3×43 Posts
Default

Quote:
Originally Posted by DukeBG View Post
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.

Last fiddled with by DukeBG on 2019-04-15 at 17:11
DukeBG is offline   Reply With Quote
Old 2019-04-15, 17:19   #472
GP2
 
GP2's Avatar
 
Sep 2003

29·89 Posts
Default

Quote:
Originally Posted by DukeBG View Post
2^3570+1 is now fully factored.
I see a C283 on FactorDB ?
GP2 is offline   Reply With Quote
Old 2019-04-15, 17:36   #473
DukeBG
 
Mar 2018

100000012 Posts
Default

Quote:
Originally Posted by GP2 View Post
I see a C283 on FactorDB ?
Your link is to 2^3750+1
DukeBG is offline   Reply With Quote
Reply

Thread Tools


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

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

Tue Oct 27 03:30:34 UTC 2020 up 47 days, 41 mins, 1 user, load averages: 1.52, 2.08, 1.90

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.