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. 
[QUOTE=lukerichards;511824]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.[/QUOTE]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 65digit factors by ECM. Most individuals do not have the resources for the first two tasks and so join cooperatives like NFS@Home To set the scale of effort required of ECM, I'm currently finding about one 45 to 50digit 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 65digit 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. 
Fire away, I'm definitely interested. Consider my expectations set and my enthusiasm undampened.
My aim is to factor 3[SUP]504206[/SUP]+1 and 3[SUP]504205[/SUP]+1 sufficiently [b]in my lifetime[/b] to provide a primality proof of 3[SUP]504206[/SUP]+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. 
[QUOTE=lukerichards;511836]My aim is to factor 3[SUP]504206[/SUP]+1 and 3[SUP]504205[/SUP]+1 sufficiently [b]in my lifetime[/b] to provide a primality proof of 3[SUP]504206[/SUP]+2. As intractable a goal as that might be, I need to start somewhere and the Cunningham project seems a sensible place to start.[/QUOTE]
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. 
[QUOTE=GP2;511978]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.
[/QUOTE] 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. 
[QUOTE=lukerichards;511980]Anyway, I'm offering to contribute to Cunningham, so let's not question why.[/QUOTE]
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. 
[QUOTE=GP2;512006]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.[/QUOTE] 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. 
[QUOTE=lukerichards;512025]Furthermore, factoring smaller 3+ Cunningham numbers will help factor the one I'm trying to factor, so it's not a completely disconnected interest.[/QUOTE] 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 PariGP 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]
[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)))[/code] 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 [i]smallest[/i] remaining cofactor is C3664. Good luck... 
[QUOTE=lukerichards;511836] My aim is to factor 3[SUP]504206[/SUP]+1 and 3[SUP]504205[/SUP]+1 sufficiently [B]in my lifetime[/B] to provide a primality proof of 3[SUP]504206[/SUP]+2.[/QUOTE]
The only reasonable hope with foreseeable technology is that someone builds a quantum computer able to factor the algebraic factors of 3[SUP]504205[/SUP]+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 
Anyone reading this thread would be forgiven for thinking nobody wants me to contribute to the Cunningham Project.

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: [url]http://factordb.com/index.php?id=1100000001124804267[/url] [url]http://factordb.com/index.php?id=1100000001122158773[/url] 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 factorfinding probability lower than the probability of grabbing two random hydrogen atoms from the universe, with replacement, and then discovering that they were the same. 
All times are UTC. The time now is 15:16. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.