Are there any Fermat numbers that might be prime?

[jasonp]

Originally Posted by R.D. Silverman

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.

This is of course what I meant. I read the original question to be wondering if computations that are currently impossible would become possible because of a different representation of the underlying data, and those computations must involve squaring at least.

One of the early papers on number-theoretic transforms claimed that you could get some computational savings when computing these transforms because multiplication by many of the constants involved in the transform could be performed with only a few modular shifts, adds and subtracts. This is something the dedicated hardware the reader is designing should take advantage of :)

[R.D. Silverman]

Originally Posted by jasonp

This is of course what I meant. I read the original question to be wondering if computations that are currently impossible would become possible because of a different representation of the underlying data, and those computations must involve squaring at least.

One of the early papers on number-theoretic transforms claimed that you could get some computational savings when computing these transforms because multiplication by many of the constants involved in the transform could be performed with only a few modular shifts, adds and subtracts. This is something the dedicated hardware the reader is designing should take advantage of :)

Yep. Dedicated custom hardware can speed things.

However, it does not change the underlying complexity. All it does
is improve the implied multiplicative CONSTANT in the O() estimates.

The true asymptotic complexity of multiplication on a Turing machine is
unknown. (see Knuth Vol 2 section on multiplication). We know that we
can achieve linear time complexity on a *pointer* machine, and that this
is the best possible, but we do not know the true lower bound on a
Turing (e.g. finite state real computer) machine. We can achieve
O(n log n loglog n) to multiply n-bit numbers, but do not know if this
is the best possible. I strongly suspect that it is, but there is no proof.

The modular reduction just slows things down by a fixed constant (the
constant being machine and implementation dependent) since we can
also do division by FFT's in time O(n log n loglog n) time. (See Aho, Hopcroft,
and Ullman's book on Algorithms for a clear exposition).

[akruppa]

The recent paper by Martin Fürer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.

Alex

[ewmayer]

Originally Posted by akruppa

The recent paper by Martin Führer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.

That sounds like a classic "strictly of theoretical interest" scenario, unless these asympotically-just-a-teensy-bit-faster algorithms are simpler to implement and lend themselves just as well to algorithmic/numeric optimization as a standard transform-based multiply, which I strongly doubt.

As anyone who has implemented a halfway decent transform-based multiply algorithm knows, real-world memory management and processor-optimization effects tend to dwarf anything beyond the n*log(n) terms, and for large vector lengths, one is typically elated to even approach the n*log(n) in practice, especially once the datasets in question significantly exceed the cache sizes on the target hardware.

Thanks for the references, though. ;)

[sghodeif]

Originally Posted by jasong

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 prove the infinity of Fermat's prime numbers and find it as big as we want,but i did not publish this until now.
Just waiting or continue to find another proof for this

I wish all the best for u and all mathematicians .

Sghodeif ,

[ewmayer]

For those not familiar with Mr. Ghodeif's alleged "proofs", some background reading to prevent another thread from getting polluted with the discussion:

http://www.mersenneforum.org/showthread.php?t=4604

http://www.mersenneforum.org/showthread.php?t=4618

http://www.mersenneforum.org/showthread.php?t=5211

http://www.mersenneforum.org/showthread.php?t=6018

http://www.mersenneforum.org/showthread.php?t=9507

Mr. Ghodeif, any future posts you make with claims of this sort which [as has been the case with all your claims to date] lack any supporting documentation will be subject to deletion.

[R. Gerbicz]

Originally Posted by akruppa

The recent paper by Martin Fürer has lowered the complexity of integer multiplication to O(n log(n) 2^(log*(n))) where log*(n) is the minimum number of logarithms you need to stack to get <= 1. Bernstein did a quick estimate that suggested that it might be competitive with Schönhage-Strassen for interesting operand sizes, i.e. a few million words or so.

Alex

Here it is his book:http://www.cse.psu.edu/~furer/Papers/mult.pdf