On Wed, 3 Mar 1999, Brian J Beesley wrote:
> > That is a remarkably bold claim. It's akin to saying that the only way of
> > finding primes is by brute force testing of all candidates.
>
> How about a clever method of computing just the last few bits of
> the residual - if we could work mod 2^64 instead of mod 2^p-1 then
> that would give essentially a *huge* speed increase, even if the
> algorithm was a great deal more complex.
>
Another thing that would work nicely (and not just for LL tests) would
be if someone figured out a way to release the carries from a large
multiplication while still in Fourier space. The you just perform an NTT,
do a modular exponentiation for each digit of the transformed array,
do whetever processing is needed to magically release the carries, and
then do an inverse NTT to get the final answer.
I've thought about something like this for a long time, but have no
idea if it's even possible.
jasonp
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
