mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2019-03-26, 12:12   #1
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

28310 Posts
Default Contributing to Cunningham Project

Hi,

I'm interested in devoting some CPU work to factoring Cunningham numbers. Unsurprisingly, to anyone who has followed my exploits, I'm interested particularly in 3+ numbers.

I can't find an obvious page on the project web page or an obvious thread on here which clearly explains how to get started. Can anyone point me in the right direction? I'm happy to write it up as a guide to others, which can be stickied if desired.
lukerichards is offline   Reply With Quote
Old 2019-03-26, 13:00   #2
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

5×1,999 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Hi,

I'm interested in devoting some CPU work to factoring Cunningham numbers. Unsurprisingly, to anyone who has followed my exploits, I'm interested particularly in 3+ numbers.

I can't find an obvious page on the project web page or an obvious thread on here which clearly explains how to get started. Can anyone point me in the right direction? I'm happy to write it up as a guide to others, which can be stickied if desired.
Above all, you should realize that finding new Cunningham factors requires a lot of computation or incredibly good luck. I tell you this not to dissuade you but to set expectations and avoid disappointment.

As a rough guide, you need to be able to factor 200 digit numbers by GNFS, 300 digits by SNFS or believe that you are likely to find 60 to 65-digit factors by ECM. Most individuals do not have the resources for the first two tasks and so join co-operatives like NFS@Home

To set the scale of effort required of ECM, I'm currently finding about one 45 to 50-digit factor (of GCWs, not Cunninghams) every few week with approximately 20 cores running 24/7. I doubt I'd find even one Cunningham factor per annum with that amount of computation. However, ECM is easy to install and easy to run in fire&forget mode. Load it up, set it going with parameters suitable for finding 65-digit factors and check on it every so often. You might get lucky.

If you are still seriously interested let us know and we'll go into detail but I've already spent enough time if your question is only out of idle curiosity.
xilman is offline   Reply With Quote
Old 2019-03-26, 17:20   #3
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

283 Posts
Default

Fire away, I'm definitely interested. Consider my expectations set and my enthusiasm undampened.

My aim is to factor 3504206+1 and 3504205+1 sufficiently in my lifetime to provide a primality proof of 3504206+2. As intractable a goal as that might be, I need to start somewhere and the Cunningham project seems a sensible place to start.

For the time being, a number of friends have signed up to Google Cloud Console to get the free credit, with no intention of using it themselves. As a result I have about $1200 of VM credit to use up. When that's all gone, I'll look into my options then.

So is NFS@Home the way forward? I've run BOINC before with PrimeGrid so I'm familiar with that.
lukerichards is offline   Reply With Quote
Old 2019-03-27, 20:09   #4
GP2
 
GP2's Avatar
 
Sep 2003

A1216 Posts
Default

Quote:
Originally Posted by lukerichards View Post
My aim is to factor 3504206+1 and 3504205+1 sufficiently in my lifetime to provide a primality proof of 3504206+2. As intractable a goal as that might be, I need to start somewhere and the Cunningham project seems a sensible place to start.
Except for extremely improbable scenarios with odds comparable to winning the lottery multiple times in a row, this goal is completely infeasible with any currently known algorithm. Not in your lifetime. Not before the heat death of the universe.

Imagine you're trying to collect a few dozen eggs. Some of them are right next to you. Some are next door. Some are across town. Some are within one day's driving distance. Some are across the ocean. Some are on the Moon. Some are on Pluto. Some are on Alpha Centauri. Some are across the galaxy. Some are in the Andromeda Galaxy.

The vast majority of the eggs you are looking for have either been found already, or are forever out of reach. A tremendous lifelong effort might find a few more eggs in the "across the ocean" category. That's the only category where your efforts, or anyone else's, can actually make a difference.
GP2 is offline   Reply With Quote
Old 2019-03-27, 20:13   #5
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

283 Posts
Default

Quote:
Originally Posted by GP2 View Post
Except for extremely improbable scenarios with odds comparable to winning the lottery multiple times in a row, this goal is completely infeasible with any currently known algorithm. Not in your lifetime. Not before the heat death of the universe.
I'm 30 years old, nobody knows what will happen in the next 50 years in terms of advances in computing power and algorithm research. Current achievements would not have been thought possible 50 years ago.Everyone needs a hobby!

Anyway, I'm offering to contribute to Cunningham, so let's not question why.
lukerichards is offline   Reply With Quote
Old 2019-03-27, 23:42   #6
GP2
 
GP2's Avatar
 
Sep 2003

2×1,289 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Anyway, I'm offering to contribute to Cunningham, so let's not question why.
The Cunningham project actually deals with much smaller exponents, around 1k rather than 500k. So the work you intend to do is entirely different.

If you actually want to contribute to the Cunningham project (i.e., very small exponents), the best way would be to join NFS@Home. A great deal of ECM has already been done there, but there might be a bit left over if you coordinate with the people who've already worked there.

On the other hand, if your heart is set on the quixotic quest for this one particular huge exponent, then it seems there's not much anyone can say to dissuade you.
GP2 is offline   Reply With Quote
Old 2019-03-28, 08:51   #7
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

283 Posts
Default

Quote:
Originally Posted by GP2 View Post
The Cunningham project actually deals with much smaller exponents, around 1k rather than 500k. So the work you intend to do is entirely different.

If you actually want to contribute to the Cunningham project (i.e., very small exponents), the best way would be to join NFS@Home. A great deal of ECM has already been done there, but there might be a bit left over if you coordinate with the people who've already worked there.

On the other hand, if your heart is set on the quixotic quest for this one particular huge exponent, then it seems there's not much anyone can say to dissuade you.
Thanks for all the information - all of which I was actually aware but I understand that you are trying to make sure I'm not approaching this with undue expectations.

I do know the fact that the TCP is focussed on exponents much smaller than mine. I'm not expecting to get the factors for the ~500k exponent through this, but my interest in this number has led me to The Cunningham Project, which is probably a more useful goal in the short term.

Furthermore, factoring smaller 3+ Cunningham numbers will help factor the one I'm trying to factor, so it's not a completely disconnected interest.
lukerichards is offline   Reply With Quote
Old 2019-03-30, 14:21   #8
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3,251 Posts
Default

Quote:
Originally Posted by lukerichards View Post
Furthermore, factoring smaller 3+ Cunningham numbers will help factor the one I'm trying to factor, so it's not a completely disconnected interest.
I looked at the factordb page for 3^504206 + 3. Dividing out the factor 3, borrowing the found prime factors from the page, fiddling a bit with a text editor, and writing a mindless Pari-GP script to exhibit the known factors as divisors of cyclotomic factors gives the following:
Code:
M = [2,2; 61,1; 139627,1; 398581,1; 180117541,1; 630728992609,1; 545454568700731,1; 1254120593677177,1; 62262627532596661,1; 85741124649607123,1; 105919308797935444986721,1];
Code:
v=divisors(504205);a=#v;cf=vector(a);for(i=1,a,f=1;m=v[i];fordiv(m,d,f*=(3^d+1)^moebius(m/d));cf[i]=f);r=#M[,1];for(i=1,a,q=cf[i];for(j=1,r,g=gcd(q,M[j,1]^M[j,2]);if(g>1,print(v[i]" "g);q=q/g));if(q>1,l=1+floor(log(q)/log(10));print(v[i]" C"l)))
1 4
5 61
13 398581
65 105919308797935444986721
7757 139627
7757 1254120593677177
7757 85741124649607123
7757 C3664
38785 180117541
38785 C14795
100841 630728992609
100841 C44395
504205 545454568700731
504205 62262627532596661
504205 C177595

Judging by the results for 9^252103 + 1, I would imagine the C's have been ECM'd to the point of all but excluding any additional factors < 10^40. So I image "will help" has become "has helped all it can." You might try ECMing the remaining C's to look for somewhat larger factors. You might get lucky and find one or more. You might even get luckier, and find a large PRP cofactor (but don't use the base 3 for a PRP test with these numbers). The smallest remaining cofactor is C3664.

Good luck...
Dr Sardonicus is offline   Reply With Quote
Old 2019-03-30, 17:13   #9
chris2be8
 
chris2be8's Avatar
 
Sep 2009

180710 Posts
Default

Quote:
Originally Posted by lukerichards View Post
My aim is to factor 3504206+1 and 3504205+1 sufficiently in my lifetime to provide a primality proof of 3504206+2.
The only reasonable hope with foreseeable technology is that someone builds a quantum computer able to factor the algebraic factors of 3504205+1. Since the largest factor is 44395 digits it will need about 148000 qubits (*after* error correction). Even if that's possible it will be *very* expensive and I've no idea how long it will take to build.

Without that you need several miraculously lucky ECM hits or a mathematical breakthrough in factoring.

Chris
chris2be8 is offline   Reply With Quote
Old 2019-04-01, 20:51   #10
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

28310 Posts
Default

Anyone reading this thread would be forgiven for thinking nobody wants me to contribute to the Cunningham Project.
lukerichards is offline   Reply With Quote
Old 2019-04-02, 12:16   #11
penlu
 
Jul 2018

22·7 Posts
Default

This thread reads to me like people telling you not to expect to find factors of 3^504205+1 or 3^504206+1. For contributing to the Cunningham project, a number of posters have indicated that signing up for NFS@Home would be the best way to go.

As for factoring 3^504205+1 and 3^504206+1, Dr. Sardonicus's post is helpful: if you take a look at the corresponding factordb pages, you can find targets for ECM:
http://factordb.com/index.php?id=1100000001124804267
http://factordb.com/index.php?id=1100000001122158773

I'd offer to help ECM some of the smaller remaining composites up to 60 digits... but not for free: as payment, I want an explanation as to why you want this particular number factored.

Edit: though I'll warn you first that going up to 60 digits on C1996 (the smallest composite amongst those remaining) has a factor-finding probability lower than the probability of grabbing two random hydrogen atoms from the universe, with replacement, and then discovering that they were the same.

Last fiddled with by penlu on 2019-04-02 at 12:27
penlu is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Cunningham ECM efforts pinhodecarlos Cunningham Tables 7 2017-12-21 13:29
Cunningham ECM Now Futile? R.D. Silverman GMP-ECM 4 2012-04-25 02:45
Cunningham Project on YouTube Batalov Cunningham Tables 0 2012-02-26 02:58
Extended Cunningham or so rekcahx Factoring 6 2011-08-19 12:45
Introduction: ECM work done on Cunningham Project composites garo Cunningham Tables 2 2005-01-20 10:06

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

Tue Jun 2 21:54:44 UTC 2020 up 69 days, 19:27, 3 users, load averages: 1.69, 1.72, 1.87

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.