New Generalized Fermat factors

[D. B. Staple]

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.

[chris2be8]

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

[D. B. Staple]

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:

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.

[VBCurtis]

Originally Posted by D. B. Staple

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.

[RichD]

Originally Posted by VBCurtis

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.

[VBCurtis]

Originally Posted by RichD

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.

[RichD]

Originally Posted by VBCurtis

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.

[LaurV]

Originally Posted by VBCurtis

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...

[chris2be8]

Originally Posted by RichD

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

[Batalov]

Two more for GF'₃:

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)

[Jatheski]

463507*2^34186+1 is a Factor of GF(34185,6)!!!!