mersenneforum.org > Math Are there any Fermat numbers that might be prime?
 Register FAQ Search Today's Posts Mark Forums Read

2007-06-18, 18:58   #12
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 Originally Posted by ewmayer 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.
Uh.......

Not to be picky, but I can compute 2^2^n + 1 on any modern computer
without *any* squarings. Of course converting it to decimal takes a bit more
work.............

2007-06-18, 19:21   #13
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

23·1,019 Posts

Quote:
 Originally Posted by ewmayer 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.
You just explained why the book is wrong. The book says you need n squarings when in fact you need 2n squarings.

2007-06-18, 20:01   #14
ewmayer
2ω=0

Sep 2002
República de California

1175510 Posts

Quote:
 Originally Posted by Prime95 You just explained why the book is wrong. The book says you need n squarings when in fact you need 2n squarings.
Ah yes, I was responding to jasong's later quote:

"According to the book 2^2^n+1 requires n squarings..."

and misinterpreted that as meaning "to calculate 2^2^n+1 requires n squarings," which would have been correct, just not relevant to the ensuing primality test of that number.

 2007-06-18, 20:16 #15 jasong     "Jason Goatcher" Mar 2005 3·7·167 Posts I was hoping people would forget my stupid mistake. The book was right, I was wrong. The mistake I made was that the example given involved F(5), when I thought it involved F(32), F(5) is 2^2^5, so requires 32 squarings. Sorry for the trouble. Last fiddled with by jasong on 2007-06-18 at 20:17
2007-06-18, 23:53   #16
m_f_h

Feb 2007

24×33 Posts

Quote:
 Originally Posted by R.D. Silverman Not to be picky, but I can compute 2^2^n + 1 on any modern computer without *any* squarings. Of course converting it to decimal takes a bit more work.............
in fact, what does mean "to compute" ?
Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ?

2007-06-19, 00:38   #17
ewmayer
2ω=0

Sep 2002
República de California

5×2,351 Posts

Quote:
 Originally Posted by m_f_h Is it admissible to store the number in a "sparse" format (e.g., only list indices of nonzero bits) ?
In effect, that's what we do when we write "Fn".

 2007-06-19, 12:57 #18 mfgoode Bronze Medalist     Jan 2004 Mumbai,India 22·33·19 Posts Records! Well Jasong if its of any help to you I will give you the results in 2004. The largest known Fermat prime is F4 = 65537. The largest known composite Fermat number is F2145351 discovered by J.B. Cosgrave on feb 21, 2003. This number has the factor 3 x 2^2145353 + 1. It has 645817 digits. Among others the program by G. Woltman was essential for the discovery. At the end of May 2003 there was a total of 214 Fermat numbers known to be composite. Mally
2007-06-19, 13:24   #19
m_f_h

Feb 2007

6608 Posts

Quote:
 Originally Posted by ewmayer In effect, that's what we do when we write "Fn".
You oversimplify a bit. I mean, { Fn } is only a very limited subset of Z. What I was suggesting is to code /any/ number, using (maybe conditionally (and maybe recursively)) a sparse format where only indices of nonzero bits are stored.
Just like its commonly done for (sparse) matrices : you can do any operation allowed in the algebra of matrices with them.
Or with polynomials: you may store them as a vector of (all) coefficients, but also as a list of the (nonzero) monomials. When calculating by hand, we usually adopt the latter.
In fact, my idea amounts to that, where any number is seen as a polynomial in 2.
Since this is only a matter of storage (and of efficiently defining the usual operations depending on the storage format), it does not affect the properties of the algebra.

PS: I think your English is getting a bit too much "franglaisé"... ;-)

Last fiddled with by m_f_h on 2007-06-19 at 13:36 Reason: + recursively, + polynomial interpretation

2007-06-19, 15:01   #20
ATH
Einyen

Dec 2003
Denmark

343410 Posts

Quote:
 Originally Posted by mfgoode At the end of May 2003 there was a total of 214 Fermat numbers known to be composite. Mally
As of June 2, 2007, 230 Fermat numbers known to be composite:

http://www.prothsearch.net/fermat.html

2007-06-19, 15:53   #21
ewmayer
2ω=0

Sep 2002
República de California

5·2,351 Posts

Quote:
 Originally Posted by R.D. Silverman Not to be picky, but I can compute 2^2^n + 1 on any modern computer without *any* squarings.
I can go one better: one can in fact perform a complete base-2 probable-prime test on any Fn without any computational hardware (other than one's brain, and one doesn't even require much of that) whatsoever.

More generally, one can use the same technique to do a base-2 probable-prime test on any number of form 2n +1 and thereby prove in elementary fashion that such a number can only possibly be prime if n is itself a power of 2.

2007-06-19, 22:01   #22
T.Rex

Feb 2004
France

16458 Posts

Quote:
 Originally Posted by ewmayer 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.
Since Pépin's test requires the same time than the LLT, one can use the Mersenne calculator: With a core2 CPU at 3GHz, it would take 3000 years to test F33. I guess that in one decade, using 16 cores instead of one, that would take about 50 years to check F33. Still too long ... If machines with 1024 cores (like Azul machines) are available at that time, then it will take about only 1 year ! 10 years to wait ...
Tony

 Similar Threads Thread Thread Starter Forum Replies Last Post ET_ FermatSearch 1 2016-08-02 19:40 ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 T.Rex Math 4 2005-05-07 08:25 devarajkandadai Math 8 2004-07-27 12:27 Axel Fox Software 14 2003-07-04 18:57

All times are UTC. The time now is 15:49.

Sun Jan 29 15:49:27 UTC 2023 up 164 days, 13:18, 0 users, load averages: 0.92, 0.98, 0.88