At 18:51:38 30/7/99 +0100, Brian J. Beesley wrote:
>Given that x^2 mod 2^p-1 can be computed very efficiently using DWT
>(getting the remaindering operation for free), it occurs to me that
>it ought to be possible to compute x^2 mod 2^p+1 just as efficiently,
>using different "magic numbers".
In fact, it is possible to compute x^2 mod k*2^n+r efficiently, and I
believe that it is possible in general to compute quickly (using the DWT)
modulo a+b where gcd(a,b)=1 and the product of unique primes dividing a*b
is small.
Colin Percival
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
