mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2021-11-08, 22:02   #1
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52×7 Posts
Lightbulb 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
JeppeSN is online now   Reply With Quote
Old 2021-11-08, 23:10   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·1,201 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
(The search will go on to megaprimes of form b^2048+1, but the bases here can be even more difficult.)
Understatement detected!
Batalov is offline   Reply With Quote
Old 2021-11-08, 23:22   #3
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10011110010012 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-11-08, 23:56   #4
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

52·7 Posts
Thumbs up

Quote:
Originally Posted by VBCurtis View Post
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
JeppeSN is online now   Reply With Quote
Old 2021-11-09, 00:03   #5
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

10,039 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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...
chalsall is offline   Reply With Quote
Old 2021-11-09, 00:22   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10011110010012 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2021-11-09, 00:44   #7
charybdis
 
charybdis's Avatar
 
Apr 2020

53910 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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 View Post
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
charybdis is offline   Reply With Quote
Old 2021-11-09, 02:10   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23·1,201 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
... 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.
Batalov is offline   Reply With Quote
Old 2021-11-09, 11:28   #9
sweety439
 
sweety439's Avatar
 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36

22·3·7·37 Posts
Default

Quote:
Originally Posted by JeppeSN View Post
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
sweety439 is offline   Reply With Quote
Old 2021-11-09, 12:56   #10
JeppeSN
 
JeppeSN's Avatar
 
"Jeppe"
Jan 2016
Denmark

101011112 Posts
Exclamation

Quote:
Originally Posted by sweety439 View Post
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
JeppeSN is online now   Reply With Quote
Old 2021-11-09, 17:06   #11
chris2be8
 
chris2be8's Avatar
 
Sep 2009

22·32·61 Posts
Default

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
chris2be8 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Today's Favorite Mega Number MattcAnderson MattcAnderson 44 2021-10-16 14:10
Since when was 4096 prime? Gordon PrimeNet 6 2015-07-04 17:30
My personal MEGA drive :) pepi37 Riesel Prime Search 5 2014-02-05 21:39
Assuming the goal is mega-primes, is base-3 better jasong jasong 1 2008-12-26 10:19
4096 P4 help wanted Tasuke Hardware 17 2002-08-23 22:06

All times are UTC. The time now is 11:19.


Sat Nov 27 11:19:08 UTC 2021 up 127 days, 5:48, 0 users, load averages: 1.87, 1.62, 1.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.