mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2019-04-02, 12:39   #12
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·7·109 Posts
Default

Quote:
Originally Posted by penlu View Post
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:
Quote:
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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-02, 14:30   #13
penlu
 
Jul 2018

348 Posts
Default

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...
penlu is offline   Reply With Quote
Old 2019-04-02, 15:06   #14
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1011111011002 Posts
Default

Quote:
Originally Posted by penlu View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-04-02, 15:11   #15
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

11716 Posts
Default

Quote:
Originally Posted by penlu View Post
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.
lukerichards is offline   Reply With Quote
Old 2019-04-02, 17:15   #16
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Quote:
Originally Posted by penlu View Post
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.
GP2 is offline   Reply With Quote
Old 2019-04-02, 20:41   #17
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

4,001 Posts
Default

Quote:
Originally Posted by GP2 View Post
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!
VBCurtis is online now   Reply With Quote
Old 2019-04-02, 21:59   #18
GP2
 
GP2's Avatar
 
Sep 2003

2·1,289 Posts
Default

Quote:
Originally Posted by lukerichards View Post
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.
GP2 is offline   Reply With Quote
Old 2019-04-03, 04:38   #19
penlu
 
Jul 2018

22×7 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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...

Last fiddled with by penlu on 2019-04-03 at 04:39
penlu is offline   Reply With Quote
Old 2019-04-03, 07:34   #20
lukerichards
 
lukerichards's Avatar
 
"Luke Richards"
Jan 2018
Birmingham, UK

32·31 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
lukerichards is offline   Reply With Quote
Old 2019-04-03, 08:33   #21
DukeBG
 
Mar 2018

3·43 Posts
Default

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.
DukeBG is offline   Reply With Quote
Old 2019-04-03, 13:08   #22
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

1011111011002 Posts
Default

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.
Dr Sardonicus 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:52.

Sat Apr 4 21:52:44 UTC 2020 up 10 days, 19:25, 0 users, load averages: 1.61, 1.55, 1.60

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.