mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-02-08, 21:09   #1
siegert81
 
Dec 2010

2×37 Posts
Default 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?
siegert81 is offline   Reply With Quote
Old 2012-02-08, 22:54   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
Originally Posted by siegert81 View Post
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?
You are joking, right?
R.D. Silverman is offline   Reply With Quote
Old 2012-02-08, 23:04   #3
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You are joking, right?
Doubtful. Most likely he is ign'nt of GPU programs available and their applications.
Just my dos centavos.
c10ck3r is offline   Reply With Quote
Old 2012-02-08, 23:49   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
Doubtful. Most likely he is ign'nt of GPU programs available and their applications.
.
Knowledge of GPU programs is irrelevant.
R.D. Silverman is offline   Reply With Quote
Old 2012-02-09, 00:10   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You are joking, right?
I don't think any current GPU has enough memory to do an FFT large enough to do p-1 or ECM on F33, but it's not in principle impossible; now that memory is cheap enough that people have 32G machines, p-1 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^30-element 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 couple-of-percent chance of proving compositude wouldn't be that onerous.
fivemack is offline   Reply With Quote
Old 2012-02-09, 00:22   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

10111011100112 Posts
Default

I suspect he is unaware of how much larger F(33) is than F(24).
rogue is offline   Reply With Quote
Old 2012-02-09, 00:47   #7
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

7·89 Posts
Default

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

Attached Files
File Type: txt Fermdig.txt (482 Bytes, 236 views)
MattcAnderson is offline   Reply With Quote
Old 2012-02-09, 01:39   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by rogue View Post
I suspect he is unaware of how much larger F(33) is than F(24).
Can't people do basic arithmetic? This is not a matter of knowing (say)
college level math. This is simple arithmetic.
R.D. Silverman is offline   Reply With Quote
Old 2012-02-09, 01:41   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by fivemack View Post
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 couple-of-percent chance of proving compositude wouldn't be that onerous.
It's been done. See, e.g. post #7
R.D. Silverman is offline   Reply With Quote
Old 2012-02-09, 07:27   #10
msft
 
msft's Avatar
 
Jul 2009
Tokyo

2·5·61 Posts
Default

Old my web page.
Attached Files
File Type: bz2 README.html.bz2 (4.3 KB, 123 views)
msft is offline   Reply With Quote
Old 2012-02-09, 08:02   #11
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2,473 Posts
Default

go there (fermatsearch) to get software dealing with fermat factors.


firejuggler is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stupid Question Re: Fermat Factor search c10ck3r Math 3 2012-10-18 05:26
Are there any Fermat numbers that might be prime? jasong Math 39 2007-10-27 23:11
best Fermat search space program wanted jasong Programming 0 2007-10-03 20:34
Generalized Fermat Prime Search? pacionet Lounge 3 2006-01-25 15:40
Status of Fermat Search rogue Factoring 13 2004-05-01 14:48

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

Wed Nov 25 23:34:55 UTC 2020 up 76 days, 20:45, 3 users, load averages: 1.03, 1.21, 1.26

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.