Are there any Fermat numbers that might be prime?

[jasong]

Please think of any of the following that are between parentheses as "subscripted."

F(0),F(1),F(2),F(3), and F(4) are all prime

F(n) for n=5 to 32 have a known factor

f(33) is the lowest one which is an unknown

Status unknown for F(n) with n-values of 33-35, 40-41,44-47,49-50

[axn]

Originally Posted by jasong

F(n) for n=5 to 32 have a known factor

Not quite.

[mfgoode]

Originally Posted by ATH

As of June 2, 2007, 230 Fermat numbers known to be composite:

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

Thank you ATH for updating my data.

Well these types of records are like grave stones. At least one is added every day and they with time disappear into oblivion !

Lets go in for more lasting things to disagree with!

BTW: I appreciate your trouble and in no way am disagreeing with you

Mally

[jasonp]

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

The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn (it's just like LL tests, Prime95 doesn't bother trying to compress the numbers it works with because it wouldn't do any good).

[ewmayer]

Originally Posted by jasonp

The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn

...except in the base-2 PRP case I mentioned above - there, the bitstrings that occur during the repeated square-and-modding are not random. But it's alas not useful for rigorously establishing primality, it only tells you which of the numbers of the general form 2ⁿ+1 *could* be prime.

[R.D. Silverman]

Originally Posted by jasonp

The trouble is not representing Fn, it is performing arithmetic modulo Fn. The things you're doing arithmetic on are random bit-strings that have the same number of bits as Fn (it's just like LL tests, Prime95 doesn't bother trying to compress the numbers it works with because it wouldn't do any good).

Huh? Computing mod F_n is *easy*. It can be done in linear time (in the
number of bits)

x mod 2^n + 1 --> Put x = A*2^n + B

then x mod 2^n+1 = A*2^n + B + A - A mod 2^n+1 =
A*(2^n+1) + B-A mod 2^n + 1 = B-A mod 2^n + 1

[m_f_h]

thanks for pleading in favour of my idea (indirectly...)

Originally Posted by R.D. Silverman

x mod 2^n + 1 --> Put x = A*2^n + B
Then x mod 2^n+1 = A*2^n + B + A - A mod 2^n+1 =
A*(2^n+1) + B-A mod 2^n + 1 = B-A mod 2^n + 1

Even easier : A * 2^n + B == A*(-1)+ B (mod 2^n+1).
A less trivial question : what are the nonzero bits of 3^k or 5^k mod Fn?
are they really random ?
if so for 3 and 5, maybe not for some other admissible "seed" (as TRex would certainly call it ;-) ?

[ewmayer]

Originally Posted by R.D. Silverman

Huh? Computing mod F_n is *easy*.

I'm pretty certain Jason P was referring to the *squaring* of a length-F_n random bitstring and/or the accompanying implicit DWT-based mod, not the trivial mod you refer to.

[R.D. Silverman]

Originally Posted by ewmayer

I'm pretty certain Jason P was referring to the *squaring* of a length-F_n random bitstring and/or the accompanying implicit DWT-based mod, not the trivial mod you refer to.

He wrote:

"The trouble is not representing Fn, it is performing arithmetic modulo Fn"

This is pretty clear. He said nothing about squaring a random bitstring.

You are referring to the difficulty of doing a multiplication, A*B. Once
one has the product doing the reduction is easy. The difficulty is getting the
product.

[ewmayer]

Originally Posted by R.D. Silverman

"The trouble is not representing Fn, it is performing arithmetic modulo Fn"

And in particular, doing multiplication. This is obvious to any one who has done any work with multiprecision arithmetic.

This is pretty clear. He said nothing about squaring a random bitstring.

In the context of testing Fermat numbers for primality, squaring a random bitstring is precisely the kind of arithmetic that dominates the computation. As I'm sure you know very well.

You are referring to the difficulty of doing a multiplication, A*B. Once
one has the product doing the reduction is easy. The difficulty is getting the
product.

Exactly, and in the present context, it seemed quite clear that this is the crux of the matter. I'm sure you make analogous context-dependent inferences when talking about e.g. NFS all the time. So why do you suddenly need things spelled out in nauseating detail when it comes to a conceptually much simpler algorithm?

[akruppa]

Originally Posted by R.D. Silverman

You are referring to the difficulty of doing a multiplication, A*B. Once
one has the product doing the reduction is easy. The difficulty is getting the
product.

Of course, nowadays hardly anyone does the full product and then reduces mod F_m any more. There's the DWT for that. Also, to me "performing arithmetic modulo F_n" was quite clearly referring to doing operations in the ring Z/F_nZ, which of course includes multiplication. Cutting a bit string in halves and subtracting them may be called reduction mod F_n, but "arithmetic" can be expected to mean more than just the reduction. And beside all that, I think Jason was merely pointing out that even though the modulus may have a simple representation, the values we are actually working with - the residues - usually do not.

Alex