Potential primality of F33, F34, and F35

[siegert81]

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.

[GP2]

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 × 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.

[ATH]

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*2³⁵ searched to k=4.8*10¹⁷ and k*2³⁶ searched to k=7*10¹⁷ and lower for k*2³⁷, k*2³⁸ etc.

Now: 7*10¹⁷ * 2³⁶ is about 2⁹⁵ so 95 bits. Compare that to F33 = 2^{8,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: ~2⁹⁵ vs 2^{17,179,869,184} and 2^{34,359,738,368}

[ATH]

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 × 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.

[ET_]

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.

[ET_]

BTW I just restarted my trial-work on n=37...

[GP2]

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.

[a1call]

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.

Thank you advance.

ETA

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?

[GP2]

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.

I would also appreciate if someone would work out the number of decimal-digits of F33.

Well, 2³³ is 8,589,934,592, so that's how many binary digits F33 has. To get the number of decimal digits, multiply that by log₁₀(2) to get 2,585,827,973.

Are F31 and F32 known to be composite?

Yes, they have known small factors.

F31 has the factor 5463561471303 × 2³³ + 1

F32 has the factor 1479 × 2³⁴ + 1

[a1call]

Thank you for taking the time to reply with such details.

[a1call]

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?
Thank you in advance.