mersenneforum.org  

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

Reply
 
Thread Tools
Old 2007-06-18, 04:54   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

DB116 Posts
Default Are there any Fermat numbers that might be prime?

First, let me say, that while I know little about number theory, I'm confident in my ability to notice seemingly odd facts, and therefore be able to ask good questions.

I've been reading in a number theory book I have(made for high school students) about Fermat numbers. In it, it states a method where, for any number 2^2^n+1, it's possible to determine, with n squarings, whether or not it's definitely composite. If anyone wishes I could attempt to post it here(I might make an error, since I don't totally understand the method), but what I was wondering is if anyone has made a program to go through the numbers to check for absolutely certain compositeness. And if so, how far have they gotten?

Last fiddled with by jasong on 2007-06-18 at 05:25
jasong is offline   Reply With Quote
Old 2007-06-18, 05:31   #2
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

For those who have been tracking all the changes I've made to the previous post, yes, I am a VERY impulsive person.

Here's the thing: I have an external hard drive with 160GB when it's totally empty. If my calculations are correct(I hope they are), I can handle the math for testing all the Fermat numbers for absolute compositeness up to F40(2^2^40+1). If anyone wants to help me attempt to do any of these numbers(in Linux, it has be done using my Linux box. I'm not going to chance screwing up my Windows box) you can PM me.
jasong is offline   Reply With Quote
Old 2007-06-18, 05:37   #3
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5·701 Posts
Default

For those of you who are interested, here's how the math works for what I want to attempt:

You have a number F(n)=2^2^n+1. You take a number a,(say, a=3)

If F(n) is prime than 3^2^n is congruent to 1 (mod F(n))

I just realized I need to refigure the maximum F(n). Be back in about 15 minutes.

Edit: I think the maximum Fermat number I can handle is F(39).

Last fiddled with by jasong on 2007-06-18 at 05:40
jasong is offline   Reply With Quote
Old 2007-06-18, 05:39   #4
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

Quote:
Originally Posted by jasong View Post
First, let me say, that while I know little about number theory, I'm confident in my ability to notice seemingly odd facts, and therefore be able to ask good questions.

I've been reading in a number theory book I have(made for high school students) about Fermat numbers. In it, it states a method where, for any number 2^2^n+1, it's possible to determine, with n squarings, whether or not it's definitely composite. If anyone wishes I could attempt to post it here(I might make an error, since I don't totally understand the method), but what I was wondering is if anyone has made a program to go through the numbers to check for absolutely certain compositeness. And if so, how far have they gotten?
I think the book says 2^n squarings...
Citrix is offline   Reply With Quote
Old 2007-06-18, 06:23   #5
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

66418 Posts
Default

Quote:
Originally Posted by Citrix View Post
I think the book says 2^n squarings...
Yes, Pepin's test requires that many squarings. The smallest Fermat number of unknown character is F33, and a squaring modulo this number requires 1GB of memory and just over 60 seconds on 2004-era hardware. You just have to do 8 billion of these :)

Last fiddled with by jasonp on 2007-06-18 at 06:27
jasonp is offline   Reply With Quote
Old 2007-06-18, 15:48   #6
kuratkull
 
kuratkull's Avatar
 
Mar 2007
Estonia

23·17 Posts
Default

This topic seems really interesting, but I don't really grasp the context, anyone care to explain it in a bit simpler terms? :)

PS!: Not a native english speaker, but understand math terms RATHER well(thanks to mersenneforum.org :D)
kuratkull is offline   Reply With Quote
Old 2007-06-18, 16:14   #7
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

Here's how Pepin's test works. Take any quadratic non-residue of a Fermat number, 3 works as well as any other. If we want to test that 2^(2^33)+1 is prime or composite, for example, we simply have to compute 3^(2^(2^33-1)) mod 2^(2^33)+1, a computation which starts with 3 and does 2^33-1 (or 8,589,934,591) squarings mod 2^(2^33)+1. If the result is -1, the Fermat number is prime, otherwise it is composite.
philmoore is offline   Reply With Quote
Old 2007-06-18, 17:06   #8
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

DB116 Posts
Default

According to the book 2^2^n+1 requires n squarings. So, not many squarings, but the length of the numbers involved doubles each time.
jasong is offline   Reply With Quote
Old 2007-06-18, 17:08   #9
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

11·19·47 Posts
Default

As others have noted, direct compositeness test of F33 is currently way out of reach, even on fast multiprocessor hardware. Once we can get the per-iteration time down into the 0.01 second range, we can contemplate such a computation. Perhaps in a decade or so.

As far as the thread title goes, any of the infinitely-many remaining "status unknown" Fermat numbers *might* be prime, but based on the data and some plausible heuristics based on the special form of the factors of such numbers and the sparseness of the candidates (compared e.g. to Mersenne numbers), the odds of this sequence yielding any more primes than the original "gang of five" are extremely small.
ewmayer is offline   Reply With Quote
Old 2007-06-18, 17:25   #10
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×3×1,193 Posts
Default

Quote:
Originally Posted by jasong View Post
According to the book 2^2^n+1 requires n squarings.
Throw the book away.

Last fiddled with by Prime95 on 2007-06-18 at 17:26
Prime95 is offline   Reply With Quote
Old 2007-06-18, 18:27   #11
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

100110010111112 Posts
Default

Quote:
Originally Posted by Prime95 View Post
Throw the book away.
No, the book is correct, 22[sup]n[/sup] needs n squarings, but that's just the Fermat number *itself* - for Pepin's test we need to raise some number (typically 3, as it's the smallest eligible candidate) to that power, which needs 2n squarings.
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
ecm with Fermat numbers ET_ FermatSearch 1 2016-08-02 19:40
P-1/P+1 on Fermat numbers ATH Operazione Doppi Mersennes 2 2015-01-25 06:27
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25
Fermat Numbers devarajkandadai Math 8 2004-07-27 12:27
Factoring Fermat Numbers Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 11:58.

Tue Nov 24 11:58:35 UTC 2020 up 75 days, 9:09, 4 users, load averages: 1.73, 1.73, 1.68

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.