20120208, 21:09  #1 
Dec 2010
2·37 Posts 
Fermat Prime search?
Considering the massive increase in speed that GPUs enable, does anyone know if there's been an effort to test the "classical" Fermat numbers for primality?
F(33), F(34), F(35), F(40), F(41), F(44), F(45), F(46), F(47), F(49), F(50), F(51)... These are all 2^2^N + 1, but no factors have been found, and primality tests have never been run. Can GeneferCUDA be used to test these numbers? 
20120208, 22:54  #2  
Nov 2003
2^{6}·113 Posts 
Quote:


20120208, 23:04  #3 
Aug 2010
Kansas
547_{10} Posts 

20120208, 23:49  #4 
Nov 2003
2^{6}×113 Posts 

20120209, 00:10  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
2·29·109 Posts 
I don't think any current GPU has enough memory to do an FFT large enough to do p1 or ECM on F33, but it's not in principle impossible; now that memory is cheap enough that people have 32G machines, p1 or ECM in core on F33 or even F34 and F35 is feasible but hard. It looks as if FFTW out of the box can compute a 2^30element FFT, which would be fine for F33.
Just checking potential factors would indeed be fairly straightforward on a GPU; probably need to write a little bit of new code because the factors are a bit bigger than for mersenne numbers, but computing 2^2^53 modulo (1..2^40)*2^51+1 wouldn't be that painful a job. Obviously an LL test is impractical, but (being charitable, because it's always best to be charitable) trial factorisation with a coupleofpercent chance of proving compositude wouldn't be that onerous. 
20120209, 00:22  #6 
"Mark"
Apr 2003
Between here and the
2^{6}×3×31 Posts 
I suspect he is unaware of how much larger F(33) is than F(24).

20120209, 00:47  #7 
"Matthew Anderson"
Dec 2010
Oregon, USA
1001011010_{2} Posts 
The 24th Fermat number has 5,050,446 digits. The next smallest Fermat number of unknown character is F(33), which has 2,585,827,973 decimal digits. So Crandall and friends were able to determine primality of a number with just over five million digits. But F(33) has two and a half billion digits.
I have been working on fermat factors of the form k*2^36 + 1. There are no factors of this form for k < 10^16. Basically, I want to find a factor of the 34th Fermat number. If someone were to write software that would do this search on a GPU, I would like that. Matt 
20120209, 01:39  #8 
Nov 2003
2^{6}×113 Posts 

20120209, 01:41  #9  
Nov 2003
2^{6}·113 Posts 
Quote:


20120209, 07:27  #10 
Jul 2009
Tokyo
2×5×61 Posts 
Old my web page.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Stupid Question Re: Fermat Factor search  c10ck3r  Math  3  20121018 05:26 
Are there any Fermat numbers that might be prime?  jasong  Math  39  20071027 23:11 
best Fermat search space program wanted  jasong  Programming  0  20071003 20:34 
Generalized Fermat Prime Search?  pacionet  Lounge  3  20060125 15:40 
Status of Fermat Search  rogue  Factoring  13  20040501 14:48 