mersenneforum.org Factoring humongous Cunningham numbers
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2006-04-08, 15:47   #1
Yamato

Sep 2005
Berlin

2·3·11 Posts
Factoring humongous Cunningham numbers

Quote:
 This thread is about factoring homogeneous Cunningham numbers, i.e. an Β± bn with coprime a and b, 2<=a
_________________________________

I found 3793240807030006427627390804715037 as a factor of 4^337 - 3^337 - maybe it is already known. Program output:

GMP-ECM 6.0.1 [powered by GMP 4.1.4] [ECM]
Using B1=1000000, B2=839549779, polynomial Dickson(3), sigma=2470101139
Step 1 took 23997ms
Step 2 took 9851ms

I know, 34 digits are not news these days - but maybe somebody is interested in it.

Last fiddled with by axn on 2019-08-08 at 06:24 Reason: Main page URL

 2006-04-08, 16:52 #2 wblipp     "William" May 2003 New Haven 23·103 Posts IIRC, Bob Silverman was working a list of an Β± bn. For numbers close to this form with known interest in the factors, Richard Brent will take factors of a337-1, with a < 10,000 and the factors > 109. At present he lists factors for only a from 2 to 10 and a=337.
2006-04-08, 23:25   #3
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by wblipp IIRC, Bob Silverman was working a list of an Β± bn. For numbers close to this form with known interest in the factors, Richard Brent will take factors of a337-1, with a < 10,000 and the factors > 109. At present he lists factors for only a from 2 to 10 and a=337.
I have done all 4^n - 3^n for n <= 261

I have done some recent work on extending 3^n +/- 2^n to n = 400.
There are about 2 dozen composites left.

2006-04-10, 14:44   #4
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 Originally Posted by R.D. Silverman I have done all 4^n - 3^n for n <= 261 I have done some recent work on extending 3^n +/- 2^n to n = 400. There are about 2 dozen composites left.

Would anyone like to take a whack at them?

2006-04-10, 16:01   #5
rogue

"Mark"
Apr 2003
Between here and the

2×53×61 Posts

Quote:
 Originally Posted by R.D. Silverman Would anyone like to take a whack at them?
If you post the composites and how much ECM has been done on each, I'm certain that one or more people would throw some resources your way.

2006-04-10, 16:47   #6
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by rogue If you post the composites and how much ECM has been done on each, I'm certain that one or more people would throw some resources your way.
I have run about 300 curves with first limit 1M (a small effort)
Here are the remaining composites with n <= 400.

3^n + 2^n

362 (2) 10840121857.C162
367 (1) 6607.13768373.208782631.17491804898039039514781661.C130
371 (1,7,53) 204389653550334425652053.C126
372 (4,12,124) 5953.C111
379 (1) C181
382 (2) 2293.398047057.C170
383 (1) 2756069.C176
386 (2) 5037855841.2420114303415642626173.2923813115488399382449.C131
388 (4) 3881.97777.C175
394 (2) 99289.347671117.182870936735296723148317.C151
400 (16,80) 19995617469086942401.C134

3^n - 2^n

335 (1,5,67) 161471.2677857341.459904255060815869460551.C88
337 (1) 9785807.C154
343 (1,7,49) 125539.C136
347 (1) 2083.4855947384634671768060977183621.C132
349 (1) 83757907.51095243093.25596540763065937603.11848591000104763324365120718891.C98
353 (1) 4943.7460934577.3939214450103.7049420316073.C130
359 (1) 719.16208386597057.231558857865697.283082202603561296656613.C118
363 (1,3,11,33,121) 2179.1061406858984187.C87
365 (1,5,73) 944621.C132
367 (1) 2203.3671.17250374783.C158
371 (1,7,53) 743.54167.C141
373 (1) 15667.2262619.249965951.C160
379 (1) 419933.885345041389532803.C158
389 (1) 9337.C182
391 (1,17,23) 4741267.C161
395 (1,5,79) 38711.C144
397 (1) 12509122229.183139575629088302014027581573180839.C145

Note that 3,2,335- and 3,2,363- are totally trivial with SNFS;
I just haven't done them.

Several others are quite easy.

2006-04-10, 19:51   #7
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

24·13·53 Posts

Quote:
 Originally Posted by R.D. Silverman I have run about 300 curves with first limit 1M (a small effort) Here are the remaining composites with n <= 400. ...] Note that 3,2,335- and 3,2,363- are totally trivial with SNFS; I just haven't done them. Several others are quite easy.
A C8x is totally trivial with MPQS too.

If it wasn't that I was too lazy (or, if you prefer the politcally correct excuse, too busy with higher prriority work) I'd do them myself. Should only take a few hours each.

Paul

2006-04-10, 20:16   #8
R.D. Silverman

Nov 2003

164448 Posts

Quote:
 Originally Posted by xilman A C8x is totally trivial with MPQS too. If it wasn't that I was too lazy (or, if you prefer the politcally correct excuse, too busy with higher prriority work) I'd do them myself. Should only take a few hours each. Paul
Yep. I use my CPU resources for 'higher prioriy stuff' as well.

These numbers are "in the grass" priority....

 2006-04-10, 21:11 #9 John Renze     Nov 2005 24·3 Posts The C87 cofactor of 3^636-2^363 factors thusly: 51367404262568392429656240517252067923 x 7705482404964763837578788370404060262063595624219 This factorization was found using Msieve v. 1.01. Last fiddled with by John Renze on 2006-04-10 at 21:15
 2006-04-10, 22:38 #10 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts [SOAPBOX] John, I would like to thank you for completing this factorization. Sometimes those of us who are committing our resources to more "cutting edge" problems forget that we also need to be grooming new researchers to take our place. Independently solving "simple" problems is both useful for the result and instructive in developing your abilities. Bob Silverman seduced me into participating in a collaborative factoring project decades ago. (At that time a 90MHz Pentium was very much "state of the art"). With his help, I established an automated collaboration to perform widely distributed sieving. NFSNet continues to help push the limits of the Cunningham Project. The "cutting edge" always requires some rather formatible resources. I was unable to perform sufficient filtering on one of our current projects on a machine with 2GB of RAM. But I hope that you have been "bitten" by the bug and will become more active in the NC community. (no, Mike, I don't mean North Carolina) Frankly, we need more new blood. At this point in life, I should ask "Should I wear the bottoms of my trousers rolled?" I'm hoping that my last "hurrah" can be a 1Kb factorization. I hope to see some younger participants ready to step in and fill the places of those who are more suited to "gardening" rather than cutting-edge math. And, to Bob and Paul, we old codgers can still teach the young whipersnappers a thing or two. (Thanks Bob for "infecting" me.) [/SOAPBOX]
 2006-04-10, 23:26 #11 John Renze     Nov 2005 24×3 Posts The factors of the C88 are: 1315651155909947565347700897218133001 1338208112877762546551051364373633349610010436196551

 Similar Threads Thread Thread Starter Forum Replies Last Post wpolly Factoring 26 2016-07-29 04:34 Xyzzy Cunningham Tables 42 2014-04-02 18:31 jasong GMP-ECM 6 2006-06-30 08:51 jasong Factoring 1 2006-04-03 17:18 jasong Factoring 27 2006-03-21 02:47

All times are UTC. The time now is 19:40.

Wed Dec 1 19:40:06 UTC 2021 up 131 days, 14:09, 1 user, load averages: 1.59, 1.52, 1.50