Hello. I'm putting the finishing touches on a large-integer convolution
library that's optimized for the Alpha ev6, and I want to build support
for Mersenne-mod convolution right into the library. However, the
library is integer-only and works with integers modulo a 62-bit prime
(eventually several 62-bit primes, once I code up Chinese remainder
convolution). This means that in order to perform DWT arithmetic I have to
find n_th roots of 2 in a finite field modulo a given prime, where n is a
large power of two.
I have no clue how to do this. Nick Craig-Wood's page gives some hints for
the special case of 2^64-2^32+1, but not enough for me to apply the theory
to other primes. It looks like you need to find primes p so that
(p-1)/(order of 2 mod p) has a large power of 2 as a factor. 62-bit primes
where this is the case seem quite rare; I've found only 14 primes of this
size that allow a Mersenne DWT of size 2^22 or more (out of a billion
candidates).
But now I need some way to figure out the actual root of two. Can anybody
point me in the right direction?
jasonp
PS: This code promises to be the fastest integer-only LL test available.
It's already producing runtimes in the ballpark of floating point code,
and will improve more when I add CRT code and optimize more heavily.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
