20211108, 22:02  #1 
"Jeppe"
Jan 2016
Denmark
2·7·13 Posts 
Help factor some b such that b^4096+1 are mega(PR)primes
While Mersenne primes can be thought of as primes that precede a perfect power, a socalled generalized Fermat prime is defined (here) as a prime following a perfect power, so a prime of form b^N+1 with b>1 and N>1. As readers of this forum will know, N must necessarily be a power of two.
For the largest N considered in searches for such primes, the resulting finds will automatically be megaprimes, i.e. have more than a million (decimal) digits. At least as early as August 2015, the idea to skip some b values in the formula b^131072+1 to get to the region of megaprimes was perceived. And quite soon the search was successful. In February 2019, I came up with the not particularly revolutionizing idea to do the same for b^65536+1, b^32768+1 and so on. This has been implemented and fruitful. However, as was certainly predicted by everyone, eventually a point was reached where the resulting b became hard to factor. This happened at exponent 4096. For this exponent, set: b_min = ceiling[10^(999999/4096)]+1 (The +1 in the formula for b_min is just there to get an even number.) The search has found that b^4096+1 is a probable prime for: b = b_min + 102242 b = b_min + 136684 b = b_min + 264748 b = b_min + 377416 The first two of these turned out to be easy to factor, and hence the corresponding PRPs are proven primes. But the last two turned out to be harder. As you can read in a PrimeGrid forum thread, a nondistributed attempt at factoring these latter two, has not led to a sufficient factorization (at least a part b^(1/3) must be factored for an N1 primality proof to work). So, is anybody interested in doing a collaborative effort (or bringing a huge computing power) to factor these two particular bases? (The search will go on to megaprimes of form b^2048+1, but the bases here can be even more difficult.) /JeppeSN 
20211108, 23:10  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23323_{8} Posts 

20211108, 23:22  #3 
"Curtis"
Feb 2005
Riverside, CA
13·421 Posts 
I read the thread you linked at PrimeGrid, and it took a while to get to the ECM summary. If I read it correctly, a T55 has been done on both the C225 and the C233, and you're hoping for help to do more ECM?
To me, it seems reasonable to ECM up to T60 or a bit more, but the resources needed to GNFS a C225 are rather substantial compared to the 'value' of the resulting primality proof. That is, you could probably find six more such primes (and prove a majority of them) with the resources it would take to factor a C225. You're looking at roughly 800 threadyears for sieving, and each sieve client process would need ~10GB memory to run. I think even a T65 worth of ECM costs more than simply finding another such prime. 
20211108, 23:56  #4  
"Jeppe"
Jan 2016
Denmark
2×7×13 Posts 
Quote:
Clearly, I am not saying this is the cheapest way to find a megaprime (for that, you can join PrimeGrid's Proth Prime Mega subproject, or their GFN17 Mega subproject, for example). I just wondered if anybody here with a knowledge of practical factorization would be interested in attempting this. Note the following: 1. We do not know if the remaining C225 and C233 have a factor with just over 55 digits. It is unlike, say, an RSA challenge number where you know in advance approximately how difficult it is going to be. 2. In case several factors remain, it may suffice to find only some of them in order to prove the milliondigit number prime. But maybe there are sufficiently many other sources of "random" numbers to factorize, like aliquot sequences etc., that these two numbers are less attractive to people? /JeppeSN 

20211109, 00:03  #5  
If I May
"Chris Halsall"
Sep 2002
Barbados
10,663 Posts 
Quote:
I spend enough time trying to explain the concept of pseudorandom to those who don't even understand the concept of collision detection in a possible execution path! Seriously. Sorry... 

20211109, 00:22  #6 
"Curtis"
Feb 2005
Riverside, CA
1561_{16} Posts 
In case several factors remain, finding one of them with ECM makes the resulting GNFS job trivial. I'm aware you don't need them all for an N1 primality proof, but in terms of the factoring job that distinction doesn't matter.
If these were, say, C200 sized where the job is simple but a bit timeconsuming, I'm fairly sure you'd find interest here. It's that both these numbers are larger than any that have been factored on this forum + NFS@home they're not interesting enough to dedicate recordbreaking resources to. As for your point #1, ECM pretesting is exactly what you do when you don't know the size of the smallest factor. My observations were meant to convey that I wouldn't do even the full ECM pretest of T70 (or more, for the C233), as the resources just don't seem "worth it". Of course, those who desire the proof may find ECM worth it into the T70 range, or may even scrounge up the ~1000 threadyears a full NFS factorization would take (~800 to sieve, 100 to 200 to run the matrix on the C225, 23x as much for the C233). I personally find T60 worthwhile for this pursuit, and may contribute some curves in a few weeks when I have some free cores. Please keep us posted here about how many curves get run larger than T55 (B1 = 110M) level. 
20211109, 00:44  #7  
Apr 2020
2^{3}·107 Posts 
Quote:
Quote:
Even if you run on slow CPUs, assume the degree6 doubling rate is the same as degree5 (it isn't), and allow for a higher duplication rate than I expected, I don't see how one gets close to 800 years for GNFS225. Maybe if you run it on NFS@Home 16e with their low lims. I may also contribute some ECM curves once 3,748+ is done sieving. Last fiddled with by charybdis on 20211109 at 00:44 

20211109, 02:10  #8  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,313 Posts 
Quote:
It has been demonstrated that 28.7% (and with a stretch even 28.2%; then it will become very slow to have a finished proof) factorization is enough to do a good CHG proof. So you would need to strip these composites down to a ~176digit remainder (which can remain composite). for b^{2048}+1 project though, you would need to factor the 489digit composites down to 350digit size. May happen or not happen. 

20211109, 11:28  #9  
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
DF9_{16} Posts 
Quote:
Last fiddled with by sweety439 on 20211109 at 11:29 

20211109, 12:56  #10  
"Jeppe"
Jan 2016
Denmark
2·7·13 Posts 
Quote:


20211109, 17:06  #11 
Sep 2009
7·11·31 Posts 
An easier way would be to make b_min a power of a known number (eg 10^244 or 10^245 since 999999/4096 is 244.140) and search for PRPs near to it on either side. That way the bases could be factored by SNFS which is relatively easy for a c244.
Or can the b_min you quote be expressed as a simple formula? For b^2048+1 I suggest choose b_min, search for primes p_min above it and check if p_min^2048+1 is PRP. That way you don't need to factor the base. Or look for number just above b_min that are easy to factor and check them. Last fiddled with by chris2be8 on 20211109 at 17:11 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Today's Favorite Mega Number  MattcAnderson  MattcAnderson  44  20211016 14:10 
Since when was 4096 prime?  Gordon  PrimeNet  6  20150704 17:30 
My personal MEGA drive :)  pepi37  Riesel Prime Search  5  20140205 21:39 
Assuming the goal is megaprimes, is base3 better  jasong  jasong  1  20081226 10:19 
4096 P4 help wanted  Tasuke  Hardware  17  20020823 22:06 