In <URL:news:local.mersenne> on Tue 04 May, Brian J Beesley wrote:
> I'm still "rather hazy" (read, totally baffled) on exactly how the
> Crandall-Fagin procedure works, so I don't know if you could adapt NTT to
> do the mod 2^p-1 automatically. But my gut feeling is that it ought to be
> possible.
It is possible. That is how my StrongARM code works. The maths for the
irrational base transform all works out provided the relevant fractional
powers of 2 exist in the field you are using (ie for a transform of length n
there must exists a number x so that x^n = 2). Whether this is the complex
field or some other Galois field it doesn't matter. This puts some
constraints on which modulus you can use... My code uses GF(2^64-2^32+1)
which works for DWTs up to 2^26 bits (67 million). The 'interesting' binary
representation of this number makes for lots of short cuts when taking the
modulus also.
--
Nick Craig-Wood
[EMAIL PROTECTED]
http://www.axis.demon.co.uk/
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
