> >7) Anyone that makes a mathematical or algorithmic breakthrough that
> >speeds up the search process. I'm talking about a doubling in search speed
> >not a 1% speedup in assembly code.
>
> I think that this would be great -- but I seriously doubt that any
> improvement will be found. We can't get any better with FP FFTs, since we
> don't have any zero-padding any more, and you've specifically disallowed
> implementational improvements. A switch to integer FFTs might be better
> for huge FFT lengths, but integer arithmetic is currently very slow
> compared to FP arithmetic, so I doubt that will end up helping.
> Really, the only hope I can see for a significant improvement is a really
> fast implementation of Schonhage-Strasen multiplication, but
> Schonhage-Strassn is almost infamously slow.
I can dream of some possibilities. For example, somebody
might find a way to easily detect whether Mp has an odd or an even
number of prime factors, without revealing the factors themselves.
We could reject all Mp with an even number of prime factors.
If the test runs quickly, this could almost double the search time.
Other potential improvements are borderline. For example,
*) Somebody finds how to parallelize the FFT using little
communication. The wall-clock time might be reduced 10-fold,
but the CPU time increased 16-fold. This could be
great for verifying a new Mersenne prime, but
does it qualify for the money?
*) Somebody finds a novel way to choose elliptic
curves modulo Mp, using the information that
its prime factors are == 1 (mod p) and that 2, -p
are quadratic residues modulo any factor of Mp.
This lets the trial division phase search 10 bits higher,
such as searching to 2^74 rather than 2^64.
Does its finder get any money?
*) Somebody finds a way to verify the output of the LL test
without a complete rerun (cf. verification of digital signatures).
If this eliminates the need for double-checks, does it qualify?
Peter Montgomery
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
