Are there any Fermat numbers that might be prime?

[R.D. Silverman]

Originally Posted by ewmayer

No, the book is correct, 2^2[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 2ⁿ 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.............

[Prime95]

Originally Posted by ewmayer

No, the book is correct, 2^2[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 2ⁿ squarings.

You just explained why the book is wrong. The book says you need n squarings when in fact you need 2ⁿ squarings.

[ewmayer]

Originally Posted by Prime95

You just explained why the book is wrong. The book says you need n squarings when in fact you need 2ⁿ 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.

[jasong]

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.

[m_f_h]

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) ?

[ewmayer]

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 "F_n".

[mfgoode]

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

[m_f_h]

Originally Posted by ewmayer

In effect, that's what we do when we write "F_n".

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é"... ;-)

[ATH]

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

[ewmayer]

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 F_n 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 2ⁿ +1 and thereby prove in elementary fashion that such a number can only possibly be prime if n is itself a power of 2.

[T.Rex]

Originally Posted by ewmayer

As others have noted, direct compositeness test of F₃₃ 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