mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > FermatSearch

Reply
 
Thread Tools
Old 2018-07-17, 22:31   #1
siegert81
 
Dec 2010

10010102 Posts
Default 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
siegert81 is offline   Reply With Quote
Old 2018-07-18, 03:57   #2
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

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
GP2 is offline   Reply With Quote
Old 2018-07-18, 04:03   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

B9816 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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
ATH is online now   Reply With Quote
Old 2018-07-18, 04:18   #4
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23×7×53 Posts
Default

Quote:
Originally Posted by GP2 View Post
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.
ATH is online now   Reply With Quote
Old 2018-07-18, 06:28   #5
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

Quote:
Originally Posted by ATH View Post
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_ is online now   Reply With Quote
Old 2018-07-18, 06:29   #6
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

25×149 Posts
Default

BTW I just restarted my trial-work on n=37...
ET_ is online now   Reply With Quote
Old 2018-07-18, 13:16   #7
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
GP2 is offline   Reply With Quote
Old 2018-07-18, 21:09   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3·643 Posts
Default

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
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
a1call is offline   Reply With Quote
Old 2018-07-18, 21:57   #9
GP2
 
GP2's Avatar
 
Sep 2003

29×89 Posts
Default

Quote:
Originally Posted by a1call View Post
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
GP2 is offline   Reply With Quote
Old 2018-07-19, 00:35   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

3×643 Posts
Default

Thank you for taking the time to reply with such details.
a1call is offline   Reply With Quote
Old 2018-07-19, 01:16   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

36118 Posts
Default

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?
Thank you in advance.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime95 potential race on WORKER_THREADS_ACTIVE and WORKER_THREADS_STOPPING Explorer09 Software 2 2017-03-09 08:17
Would you give up your cat ownership if it increased your potential virility? jasong jasong 21 2016-05-28 09:59
A potential cause of Windows low-memory messages cheesehead Software 14 2013-05-16 00:45
Low-Stress Job with High Potential? Mathematician cheesehead Lounge 20 2009-06-05 20:24
Formula to calculate number of potential factors? Fusion_power Miscellaneous Math 13 2005-10-24 17:58

All times are UTC. The time now is 21:23.

Mon Oct 26 21:23:36 UTC 2020 up 46 days, 18:34, 0 users, load averages: 2.15, 1.91, 1.83

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