mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2015-09-10, 14:12   #133
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

23×7 Posts
Default

These factorizations may be of interest to you:

8269^64 + 1 = 2 * 918268289 * 1044636673 * 27246569091713 * 330833653243776747964260771073 * 561890619505467417673578437249 * 22086806450819711302131630421735078367489 * 105934871592905257020705756143502134929049089 * 2292352902418162653788885412662352475559184256083067753620867701690641009153

460794822529^16 + 1 = 2 * 449 * 1153 * 224916338770049 * 5105921 * 389376737 * 233934808867765849950955026670045288476891302877629398472959953431198372257 * 38146602286961890605993948856974597290093265751212822436540098028242686596033

1136051159041^16 + 1 = 2 * 1889 * 9697 * 182657 * 1029233737591167061546404353 * 4991684400616824504643310216842312333983399021237982836112814552942824158689 * 223907903336764894448936105343784675277998190020105903822837625065223158354273

4219^64 + 1 = 2 * 641 * 1231149359617 * 359087389210482358273 * 47752688172237420031803545474157444702209 * 23905514849892476878667017966491475670464026031612378017268608727472758893569 * 15940971165884654293284337615436265671765632544321819539512208108813863512200961

1951^64 + 1 = 2 * 194823352251896321 * 5494903108627806024727424919107197441 * 202922654588164636965150039799151256762741981380536283306185198707673601 * 8679678916537243713117894814798421549692233950654818824374118595670136020932975203841

844734922753^16 + 1 = 2 * 11791364666078069125878775157281 * 42723450197711698022080547608002464275357153 * 66721653457086290019387247308738749397818644599571774538173279964206603452183917936744929089886575563256181290341377

381053332094977^16 + 1 = 2 * 97 * 8161 * 48193 * 2363393 * 7490371880343553 * 3561057220214818417811213269433920961 * 2205668062227165765587303425983768752328380602786776891201714602024637217 * 18624504053661432461756375938038441455140478620001566417771989642079451879522589698595877537

2437^64 + 1 = 2 * 257 * 50017651735988471295617 * 193033328300995328225784833 * 1653341336520595851600373108168771865756446751677205428506170372737 * 699314651919694529187619943356739714360111937971028210410414814371362999644527262590546130815248769

These are numbers that I helped my friend Karl Dilcher factor, for a recent paper John Cosgrave and he wrote together. John and Karl found all the smaller factors using a combination of Maple's ifactor command and GMP-ECM. (Maple's ifactor is a composite tool analogous to YAFU.) The largest two factors of each were found by me using GNFS via CADO-NFS.

I posted these factorizations to factordb.com this morning. The size of the composite co-factors I split using GNFS were 120, 151, 154, 156, 157, 160, 164, and 166 digits, respectively.
D. B. Staple is offline   Reply With Quote
Old 2015-09-10, 15:31   #134
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22×32×5×11 Posts
Default

Some of them look easier to factor with SNFS than with GNFS. Eg 2437^64+1 could be done as SNFS 217, which would certainly be easier than GNFS 166.

Chris
chris2be8 is offline   Reply With Quote
Old 2015-09-10, 19:30   #135
D. B. Staple
 
D. B. Staple's Avatar
 
Nov 2007
Halifax, Nova Scotia

5610 Posts
Default

Quote:
Some of them look easier to factor with SNFS than with GNFS. Eg 2437^64+1 could be done as SNFS 217, which would certainly be easier than GNFS 166.
Yes, I was aware of that possibility when I was running the calculations, but decided to just use GNFS, as I was mostly interested in learning about GNFS, how to use CADO effectively, etc. However, how do you feel about the following 184-digit factor of 13^(2^8)+1:
Code:
3568837085257085726824324669332592915896684118818002242725852271403699379973925779342112031319428799393062121644906533510640858417589809041565976926535365031587312322325198092302028289
184 digits is well out of range for GNFS for me, and at 286 digits, I didn't think I could do the original number by SNFS, but I don't know much about SNFS / how to estimate SNFS difficulty, etc.

I've hit it with ECM up to 60 digits.
D. B. Staple is offline   Reply With Quote
Old 2015-09-10, 20:20   #136
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23×577 Posts
Default

Quote:
Originally Posted by D. B. Staple View Post
184 digits is well out of range for GNFS for me, and at 286 digits, I didn't think I could do the original number by SNFS, but I don't know much about SNFS / how to estimate SNFS difficulty, etc.

I've hit it with ECM up to 60 digits.
I use 5/9(snfs difficulty) +30 to estimate equivalent GNFS difficulty. The heuristic produces 188 or 189, suggesting GNFS would be more efficient for this task. However, I've only used the conversion for SNFS projects in 200-230 difficulty range, and don't know how well it extends to big-iron tasks.
VBCurtis is offline   Reply With Quote
Old 2015-09-10, 20:45   #137
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

1100101010012 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I use 5/9(snfs difficulty) +30 to estimate equivalent GNFS difficulty. The heuristic produces 188 or 189, suggesting GNFS would be more efficient for this task.
Am I missing something?
189 < 222 (remaining composite) which means SNFS would be quicker.
Now, which poly would be the best?
13 * (13^51)^5 + 1
(13^43)^6 + 13^2

Edit: Never mind, FDB doesn't have all the factors.

Last fiddled with by RichD on 2015-09-10 at 20:47
RichD is offline   Reply With Quote
Old 2015-09-11, 02:13   #138
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

23·577 Posts
Default

Quote:
Originally Posted by RichD View Post
Am I missing something?
189 < 222 (remaining composite) which means SNFS would be quicker.
Now, which poly would be the best?
13 * (13^51)^5 + 1
(13^43)^6 + 13^2

Edit: Never mind, FDB doesn't have all the factors.
Pretty sure the sextic would win by a wide margin; maybe I'll test-sieve 15e/33 to confirm.

I trusted OP's "184 digit cofactor" info.
VBCurtis is offline   Reply With Quote
Old 2015-09-11, 02:40   #139
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

7·463 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
Pretty sure the sextic would win by a wide margin; maybe I'll test-sieve 15e/33 to confirm.
I tend to agree with you since the sextic is only elevated by a little over SNFS difficulty of 2.

I felt silly after posting and discovering my error.
RichD is offline   Reply With Quote
Old 2015-09-11, 03:11   #140
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×52×61 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
I use 5/9(snfs difficulty) +30 ...
that is wrong, you should use 32, and not 30... and I think the fraction is reverted, too...
LaurV is offline   Reply With Quote
Old 2015-09-11, 15:38   #141
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22×32×5×11 Posts
Default

Quote:
Originally Posted by RichD View Post
Edit: Never mind, FDB doesn't have all the factors.
It does now. I put the C184 D B Staple posted above in as a factor and it soon worked out the missing P38 factor.

Chris
chris2be8 is offline   Reply With Quote
Old 2016-03-04, 01:59   #142
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33·73 Posts
Default

Two more for GF'3:
Code:
GF(185,3) has a factor: 1784229339435*2^187+1 = 349993408840477174486123493730674197138441859438238753954983502151681 
[TF:227:228:mmff-gfn3 0.28 mfaktc_barrett236_F160_191gs]

GF(208,3) has a factor: 4043684821205*2^209+1 = 3326950900831706864163191125935852440699815370218131646884454206899444776961 
[TF:250:251:mmff-gfn3 0.28 mfaktc_barrett252_F192_223gs]   
(the second factor is at the top of the extended range, - nearly 252 bits long)

Last fiddled with by Batalov on 2016-03-06 at 07:29
Batalov is offline   Reply With Quote
Old 2016-05-04, 22:54   #143
Jatheski
 
Jatheski's Avatar
 
Apr 2012
993438: i1090

2·73 Posts
Default

Code:
463507*2^34186+1 is a Factor of GF(34185,6)!!!!
Jatheski is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Fermat numbers (in our case primes) pepi37 Conjectures 'R Us 4 2015-10-09 14:49
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers primus Miscellaneous Math 1 2015-03-25 22:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Generalized Fermat Numbers ET_ Programming 4 2008-06-23 07:59
Generalized Fermat Prime Search? pacionet Lounge 3 2006-01-25 15:40

All times are UTC. The time now is 21:56.

Thu Jan 21 21:56:31 UTC 2021 up 49 days, 18:07, 0 users, load averages: 1.93, 2.21, 2.26

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.