mersenneforum.org Potential primality of F33, F34, and F35
 Register FAQ Search Today's Posts Mark Forums Read

 2018-07-17, 22:31 #1 siegert81   Dec 2010 2·37 Posts Potential primality of F33, F34, and F35 F33, F34, and F35 are the smallest Fermat numbers (of unknown primality) that could be prime. I'm assuming that various researchers have attempted to factor them and that their attempts have been considerably deep. Given they have effectively ruled out many small potential factors, what are the "probabilities" that these numbers are prime? I'm most interested in the "probability" that F33 is prime given that it has no (relatively) small factors. Last fiddled with by siegert81 on 2018-07-17 at 22:36
 2018-07-18, 03:57 #2 GP2     Sep 2003 A1916 Posts Lack of small factors doesn't mean much. After all, for Mersenne numbers in the typical ranges we work on, we find small factors for only about 60% of them. For the rest we have to do Lucas-Lehmer tests, but nearly all of them test composite and Mersenne primes are exceedingly rare. For Fermat numbers the counterpart to the Lucas-Lehmer test is the Pépin test, but F33 has an exponent of about 8.6 billion so it's just too big to do this test on the current generation of computers. I'd imagine that the odds of finding a Fermat prime decrease as the exponent increases, similar to what is observed for Mersenne numbers. For Mersennes we have the Wagstaff conjecture which matches the existing data pretty well. At each order of magnitude the number of Mersenne primes is roughly the same: we expect to find as many primes with exponent between 1,000 and 10,000 as the number with exponent between 1 million and 10 million or between 1 billion and 10 billion. At some point in the future it may become practical to do ECM testing on F33, but not yet. The largest Fermat number for which ECM testing is practicable is F29, with an exponent of about 537 million, which already has a known small factor = 1120049 × 229+2 + 1. I have been doing some ECM testing on it to try to find a second factor, but it takes about 120GB of memory and about a week to do a single ECM curve for F29. Last fiddled with by GP2 on 2018-07-18 at 04:26
2018-07-18, 04:03   #3
ATH
Einyen

Dec 2003
Denmark

2×1,583 Posts

Quote:
 Originally Posted by siegert81 I'm assuming that various researchers have attempted to factor them and that their attempts have been considerably deep. Given they have effectively ruled out many small potential factors, what are the "probabilities" that these numbers are prime?
It might have been "deep" factoring considering the amount of work it took, but comparing to the size of F33, F34 and F35 it is close to nothing:
http://www.prothsearch.com/fermat.html#Search

For F33: k*235 searched to k=4.8*1017 and k*236 searched to k=7*1017 and lower for k*237, k*238 etc.

Now: 7*1017 * 236 is about 295 so 95 bits. Compare that to F33 = 28,589,934,592 + 1. So it has been factored (almost) up to the 90,000,000th root of F33.
For a Mersenne number in the 90M range the 90,000,000th root is 2, so that would correspond to no factoring at all on a 90M exponent.

For F34 and F35 it is even worse: ~295 vs 217,179,869,184 and 234,359,738,368

Last fiddled with by ATH on 2018-07-18 at 04:05

2018-07-18, 04:18   #4
ATH
Einyen

Dec 2003
Denmark

2×1,583 Posts

Quote:
 Originally Posted by GP2 At some point in the future it may become practical to do ECM testing on F33, but not yet. The largest Fermat number for which ECM testing is practicable is F29, with an exponent of about 537 million, which already has a known small factor = 1120049 × 229+2 + 1. I have been doing some ECM testing on it to try to find a second factor, but it takes about 120GB of memory and about a week to do a single ECM curve for F29.
It does not *need* 120GB, because I did a few curves a while back and I only have 32 GB RAM. It took ~95 hours with all 8 cores on Haswell-E assigned to it, but I am not sure how much effect many cores have on ECM tests.

2018-07-18, 06:28   #5
ET_
Banned

"Luigi"
Aug 2002
Team Italia

12DA16 Posts

Quote:
 Originally Posted by ATH It does not *need* 120GB, because I did a few curves a while back and I only have 32 GB RAM. It took ~95 hours with all 8 cores on Haswell-E assigned to it, but I am not sure how much effect many cores have on ECM tests.
Not as efficient as a LL test, but quite better than a single core in my tests.

 2018-07-18, 06:29 #6 ET_ Banned     "Luigi" Aug 2002 Team Italia 2·19·127 Posts BTW I just restarted my trial-work on n=37...
2018-07-18, 13:16   #7
GP2

Sep 2003

50318 Posts

Quote:
 Originally Posted by ATH It does not *need* 120GB, because I did a few curves a while back and I only have 32 GB RAM. It took ~95 hours with all 8 cores on Haswell-E assigned to it, but I am not sure how much effect many cores have on ECM tests.
I am using a single core, and stage 2 takes about 40 hours and uses 95% of the memory. No doubt it could use less memory at the expense of taking extra time. Stage 1 takes about five days.

The machine is an r4.4xlarge on AWS, with eight cores. The "R" instance types have much more memory than the "C" types but slower processors. I'm using the other seven cores to do ECM on small Mersenne numbers because I worried that the Fermat ECM wouldn't use all eight cores cost-effectively. I didn't actually try it though, maybe I will.

2018-07-18, 21:09   #8
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,087 Posts

I would appreciate if someone would confirm that F33 is the smallest Fermat number with unknown primality status.

I would also appreciate if someone would work out the number of decimal-digits of F33.
I keep running out of memory computing it.

ETA
Quote:
 Now we know that all of the Fermat numbers are composite for the other n less than 31
http://primes.utm.edu/glossary/xpage/FermatNumber.html

Are F31 and F32 known to be composite?

Last fiddled with by a1call on 2018-07-18 at 21:25

2018-07-18, 21:57   #9
GP2

Sep 2003

50318 Posts

Quote:
 Originally Posted by a1call I would appreciate if someone would confirm that F33 is the smallest Fermat number with unknown primality status.
Yes. Factors are known for all Fermat numbers smaller than that, other than F20 and F24, but those two are known to be composite by the Pépin test, which is the counterpart to the Lucas-Lehmer test.

Quote:
 I would also appreciate if someone would work out the number of decimal-digits of F33.
Well, 233 is 8,589,934,592, so that's how many binary digits F33 has. To get the number of decimal digits, multiply that by log10(2) to get 2,585,827,973.

Quote:
 Are F31 and F32 known to be composite?
Yes, they have known small factors.

F31 has the factor 5463561471303 × 233 + 1

F32 has the factor 1479 × 234 + 1

 2018-07-19, 00:35 #10 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2,087 Posts Thank you for taking the time to reply with such details.
2018-07-19, 01:16   #11
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

2,087 Posts

Quote:
 It is possible that the only primes of this form are 3, 5, 17, 257 and 65,537. Indeed, Boklan and Conway published in 2016 a very precise analysis suggesting that the probability of the existence of another Fermat prime is less than one in a billion.[7]
https://en.m.wikipedia.org/wiki/Fermat_number

How is that not meaningless, given that there are infinite number of Fermat numbers?

 Similar Threads Thread Thread Starter Forum Replies Last Post Explorer09 Software 2 2017-03-09 08:17 jasong jasong 21 2016-05-28 09:59 cheesehead Software 14 2013-05-16 00:45 cheesehead Lounge 20 2009-06-05 20:24 Fusion_power Miscellaneous Math 13 2005-10-24 17:58

All times are UTC. The time now is 17:51.

Sat Sep 25 17:51:22 UTC 2021 up 64 days, 12:20, 0 users, load averages: 1.62, 2.00, 2.20