Contributing to Cunningham Project

[Dr Sardonicus]

Originally Posted by 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.
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.

This may be found in a 2018-04-25, 13:16 post here:

I'm working on factoring because I'm seeking to prove the primality of 3^504206+2.

Calling this number N, we have N - 1 = 3^504206 + 1, and N + 1 = 3*(3^504205 + 1). And, of course, factoring N - 1 and/or N + 1 "sufficiently" can give a primality proof.

So the reason for wanting these factorizations is clear enough. I'm sure having at least one of the smaller remaining composites ECM'ed beyond current limits would be appreciated.

[penlu]

At risk of being the 5-year-old with the "why"s, I want to know why the poster wants to know that that number is prime...

[Dr Sardonicus]

Originally Posted by penlu

At risk of being the 5-year-old with the "why"s, I want to know why the poster wants to know that that number is prime...

Beyond that it tested as a PRP, I don't know.

There are, of course, methods for proving N prime other than those involving the factorization of N - 1 or N + 1. It is possible that one or more of them might be better suited to the purpose that the factorization approach.

In the almost year-old thread, and in subsequent threads, it has been pointed out that the remaining composites are much larger than composites on "most-wanted" lists. This one is for remaining factors of Cunningham numbers.

The "most wanted" is 2^1207 - 1, a C337.

[lukerichards]

Originally Posted by penlu

At risk of being the 5-year-old with the "why"s, I want to know why the poster wants to know that that number is prime...

It's a good question and one I don't mind answering at all!

So this PRP is one I discovered in March 2018. I'm a high school teacher so in order to induce some interest in primes among my classes I had all 240568 digits printed on a huge poster and put up in my classroom. It's great, the kids love it. Every now and again a kid takes a real interest in primes and goes away and looks into them, coming back having found out that large primes are very hard to prove and asks if I've proved it.

I always say 'no', but some kids ask me how I'm doing with proving it. Obviously the answer is usually 'not very far' but I like to have something to explain what I'm doing to try. Saying "it's practically impossible, I've pretty much given up" doesn't give the kind of message to the kids I want to give them about not giving up etc. (I'm sure others will argue that I should be teaching kids to be realistic about their goals etc, which I do agree with but it's a nuance that would be lost on teenagers. They would just hear 'i've given up' which I don't believe is a great message to give them.

[GP2]

Originally Posted by penlu

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.

Wait... why so low probability for even a single factor of up to 60 digits?

The C1996 is (3^4462+1)*10/(3^194+1)/(3^46+1)/135641573315088856753

Surely (3^4462+1) hasn't been ECM'd to anywhere near t=60. I was finding numerous factors for 3+ with prime exponents in low ranges as recently as a few months ago with a mere t=25.

Just one example, the 28-digit factor 3,1637,+,4426039274041115597684571331 was unknown to FactorDB before December of last year and was also unknown to the Brent tables (myfactors.mooo.com). Not sure who found that one, it wasn't me.

[VBCurtis]

Originally Posted by GP2

Wait... why so low probability for even a single factor of up to 60 digits?

I suspect penlu conflated "find a factor" with "fully factor". The usual heuristic of a 1/n chance to find an n-digit factor should still apply; the catch is that the cofactor is highly likely to be composite, so finding a factor in the 40 to 60 digit range with ECM, while cool, is highly unlikely to help one along the way to "fully factored". No idea where penlu got the 1/10^85ish chance, though; a single newfound factor has a higher chance than that to result in a prime cofactor!

[GP2]

Originally Posted by lukerichards

Saying "it's practically impossible, I've pretty much given up" doesn't give the kind of message to the kids I want to give them about not giving up etc. (I'm sure others will argue that I should be teaching kids to be realistic about their goals etc, which I do agree with but it's a nuance that would be lost on teenagers. They would just hear 'i've given up' which I don't believe is a great message to give them.

You have set yourself a task equivalent to winning the lottery.

If you actually won, it would be due to sheer incredible luck and not hard work or perseverance. And that would still be true even if you'd been diligently spending £100 on lottery tickets every week without fail for your entire life.

So how does that send a positive message?

The lottery analogy breaks down somewhat because technological advances will steadily improve the odds over time, as others have pointed out. But probably not enough to make a difference in your lifetime, unless you make a fortune and spend it all on your deathbed.

[penlu]

Originally Posted by VBCurtis

I suspect penlu conflated "find a factor" with "fully factor". The usual heuristic of a 1/n chance to find an n-digit factor should still apply; the catch is that the cofactor is highly likely to be composite, so finding a factor in the 40 to 60 digit range with ECM, while cool, is highly unlikely to help one along the way to "fully factored". No idea where penlu got the 1/10^85ish chance, though; a single newfound factor has a higher chance than that to result in a prime cofactor!

Big mistake, I was looking at a probability of being about-60-digit-smooth, obviously far smaller than factor finding probability. And I'm off by thirty orders even then. No idea why all of that didn't trip all kinds of ballpark violation alarms in my head...

[lukerichards]

Originally Posted by GP2

You have set yourself a task equivalent to winning the lottery.

If you actually won, it would be due to sheer incredible luck and not hard work or perseverance. And that would still be true even if you'd been diligently spending £100 on lottery tickets every week without fail for your entire life.

So how does that send a positive message?

Because I do not live in the real world between the hours of 8.30 and 15.30. I live in the world inhabited by teenagers, who are not experts in maths or number theory and are just starting out on their mathematical journey. Your or I might know the futility of this endeavour, we might understand the true scale of the number we're talking about here but at this point they don't. They see a number and a role model they look up to and that he has faced a difficult problem but hasn't yet given up with it.

I do completely get what you are saying though - there's a message about being realistic about our challenges, setting achievable goals which is also important. However, it's important to realise and appreciate that as a high school teacher the biggest challenge we often face is "this is difficult, I give up" and I'm modelling the behaviour I want to see from them.

[DukeBG]

I, for one, approve your stance and desire to prove this number no matter how futile and improbable that is. Though I don't really like kids, this not giving up example is important for a teacher.

But yeah, as others said, helping the Cunningham project doesn't directly or even indirectly help unless you're working with ECM on specific remaining cofactors (C1996, C2329, C10253 and maybe C225698 too from 3^504206+1 and C3664, C14795, C44395 and maybe C177595 too from 3^504205+1), which Cunningham project currently doesn't and wouldn't for probably a long time. This reply in another thread was a good outline of chances and directions for the hobby project future.

[Dr Sardonicus]

Just by way of "not giving up," It occurred to me to wonder if you had checked, for your PRP number N = 3^504206 + 2, and some base b,

gcd(N, Mod(b,N)^((N-1)/f) - 1), and

f = each known prime factor of 3^504206 + 1 and also (just for the sake of thoroughness)

f = each composite cofactor with no known proper factors.