Contributing to Cunningham Project

[lukerichards]

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.

[xilman]

Originally Posted by lukerichards

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.

[lukerichards]

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

My aim is to factor 3⁵⁰⁴²⁰⁶+1 and 3⁵⁰⁴²⁰⁵+1 sufficiently in my lifetime to provide a primality proof of 3⁵⁰⁴²⁰⁶+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.

[GP2]

Originally Posted by lukerichards

My aim is to factor 3⁵⁰⁴²⁰⁶+1 and 3⁵⁰⁴²⁰⁵+1 sufficiently in my lifetime to provide a primality proof of 3⁵⁰⁴²⁰⁶+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.

[lukerichards]

Originally Posted by GP2

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.

[GP2]

Originally Posted by lukerichards

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.

[lukerichards]

Originally Posted by GP2

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.

[Dr Sardonicus]

Originally Posted by lukerichards

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:

M = [2,2; 61,1; 139627,1; 398581,1; 180117541,1; 630728992609,1; 545454568700731,1; 1254120593677177,1; 62262627532596661,1; 85741124649607123,1; 105919308797935444986721,1];

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

[chris2be8]

Originally Posted by lukerichards

My aim is to factor 3⁵⁰⁴²⁰⁶+1 and 3⁵⁰⁴²⁰⁵+1 sufficiently in my lifetime to provide a primality proof of 3⁵⁰⁴²⁰⁶+2.

The only reasonable hope with foreseeable technology is that someone builds a quantum computer able to factor the algebraic factors of 3⁵⁰⁴²⁰⁵+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

[lukerichards]

Anyone reading this thread would be forgiven for thinking nobody wants me to contribute to the Cunningham Project.

[penlu]

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.