mersenneforum.org Help factor some b such that b^4096+1 are mega(PR)primes
 Register FAQ Search Today's Posts Mark Forums Read

 2021-11-08, 22:02 #1 JeppeSN     "Jeppe" Jan 2016 Denmark 24×11 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 so-called 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 N-1 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
2021-11-08, 23:10   #2
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

11·19·47 Posts

Quote:
 Originally Posted by JeppeSN (The search will go on to megaprimes of form b^2048+1, but the bases here can be even more difficult.)
Understatement detected!

 2021-11-08, 23:22 #3 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5,279 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 thread-years 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.
2021-11-08, 23:56   #4
JeppeSN

"Jeppe"
Jan 2016
Denmark

24·11 Posts

Quote:
 Originally Posted by VBCurtis 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 thread-years 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.
Thank you for providing some insightful numbers.

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 GFN-17 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 million-digit 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

2021-11-09, 00:03   #5
chalsall
If I May

"Chris Halsall"
Sep 2002

35·43 Posts

Quote:
 Originally Posted by JeppeSN But maybe there are sufficiently many other sources of "random" numbers to factorize...
Please forgive me for this, but *_please_* don't put "quotes" around the word Random.

I spend enough time trying to explain the concept of pseudo-random to those who don't even understand the concept of collision detection in a possible execution path!

Seriously. Sorry...

 2021-11-09, 00:22 #6 VBCurtis     "Curtis" Feb 2005 Riverside, CA 5,279 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 N-1 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 time-consuming, 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 record-breaking 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 thread-years a full NFS factorization would take (~800 to sieve, 100 to 200 to run the matrix on the C225, 2-3x 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.
2021-11-09, 00:44   #7
charybdis

Apr 2020

70210 Posts

Quote:
 Originally Posted by VBCurtis 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 N-1 primality proof, but in terms of the factoring job that distinction doesn't matter.
Just to be clear for those who don't spend much time here, Curtis is using the word "trivial" similarly to how some mathematics lecturers use it, i.e. "you might be able to do this by yourself in a few weeks".

Quote:
 Originally Posted by VBCurtis Of course, those who desire the proof may find ECM worth it into the T70 range, or may even scrounge up the ~1000 thread-years a full NFS factorization would take (~800 to sieve, 100 to 200 to run the matrix on the C225, 2-3x as much for the C233).
800 thread-years for sieving is surely way too high. The correct figure is probably under 200 if your CPUs are fast enough. c225 is less than a doubling above Ryan's recent c220 for which I estimated ~100 CPU-years. RSA-240 took ~800 CPU-years to sieve, though they did get a speedup from batch smoothness detection.
Even if you run on slow CPUs, assume the degree-6 doubling rate is the same as degree-5 (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 GNFS-225. 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 2021-11-09 at 00:44

2021-11-09, 02:10   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

982310 Posts

Quote:
 Originally Posted by JeppeSN ... has not led to a sufficient factorization (at least a part b^(1/3) must be factored for an N-1 primality proof to work).
I can help by saving you a few percent. You don't need 1/3.
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 C--H-G proof. So you would need to strip these composites down to a ~176-digit remainder (which can remain composite).

for b2048+1 project though, you would need to factor the 489-digit composites down to 350-digit size. May happen or not happen.

2021-11-09, 11:28   #9
sweety439

"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

23×32×47 Posts

Quote:
 Originally Posted by JeppeSN b = b_min + 264748 b = b_min + 377416 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 N-1 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?
I have reported the last two numbers to top PRPs (since they are not proven primes), I linked your page in "Additional comments", and since I do not know the discover, I choose "Anonymous" for "Choose your name".

Last fiddled with by sweety439 on 2021-11-09 at 11:29

2021-11-09, 12:56   #10
JeppeSN

"Jeppe"
Jan 2016
Denmark

24×11 Posts

Quote:
 Originally Posted by sweety439 I have reported the last two numbers to top PRPs (since they are not proven primes), I linked your page in "Additional comments", and since I do not know the discover, I choose "Anonymous" for "Choose your name".
It is not "my page". The page is on a BOINC server set up by user stream who runs this project. /JeppeSN

 2021-11-09, 17:06 #11 chris2be8     Sep 2009 13·179 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 2021-11-09 at 17:11

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 44 2021-10-16 14:10 Gordon PrimeNet 6 2015-07-04 17:30 pepi37 Riesel Prime Search 5 2014-02-05 21:39 jasong jasong 1 2008-12-26 10:19 Tasuke Hardware 17 2002-08-23 22:06

All times are UTC. The time now is 13:03.

Sat May 21 13:03:02 UTC 2022 up 37 days, 11:04, 0 users, load averages: 1.80, 1.58, 1.54