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

2007-06-21, 12:44   #34
jasonp
Tribal Bullet

Oct 2004

355510 Posts

Quote:
 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 :)

2007-06-21, 12:55   #35
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22·1,877 Posts

Quote:
 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).

 2007-06-22, 17:42 #36 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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 Last fiddled with by akruppa on 2007-07-19 at 13:37 Reason: Corrected spelling of Fürer
2007-06-22, 18:35   #37
ewmayer
2ω=0

Sep 2002
República de California

101101111010112 Posts

Quote:
 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. ;)

2007-10-23, 18:39   #38
sghodeif

Sep 2005

2×32 Posts
yes, we prove this and find it as big as we want.

Quote:
 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 ,

 2007-10-23, 19:55 #39 ewmayer ∂2ω=0     Sep 2002 República de California 5·2,351 Posts 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. Last fiddled with by ewmayer on 2007-10-23 at 20:20
2007-10-27, 23:11   #40
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

32·179 Posts

Quote:
 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

 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 18:20.

Sat Feb 4 18:20:32 UTC 2023 up 170 days, 15:49, 1 user, load averages: 0.89, 1.00, 0.94