> Can someone tell me the details of how the discreet weighted transform
> works, or tell me where to find information on this subject.
It is described in an article by Crandall et al in Mathematics
of Computation earlier this decade.
We can use the FFT to multiply two polynomials of
degree at most n-1, getting their product modulo X^n - 1.
If the inputs are the digits of a multiple-precision integer
in radix R, then we get a product modulo R^n - 1
after carry propagation.
But we want a product modulo 2^p - 1.
The usual workaround is to force R^n - 1 > (2^p - 2)^2,
so the product will not exceed R^n - 2.
Instead the discrete weighted transform (DWT)
uses an irrational radix R = 2^(p/n). The coefficients
of the polynomials being multiplied are no longer integers.
Rather the coefficient of X^i is an integer multiple of
2^(k/n) where 0 <= k < n and k == -i*p (mod n).
This trick lets us make n half as large as we would without the DWT.
For example, if n = 4 and p = 13, then R = 2^(13/4),
R^2 = 2^(13/2), R^3 = 2^(39/4). The integer
1998 = 1024 + 7*128 + 4*16 + 14 could be represented as
2^(3/4)*R^3 + 7*2^(1/2)*R^2 + 4*2^(1/4)*R + 14
with [14, 4*2^(1/4), 7*2^(1/2), 2^(3/4) ]
being the input coefficients to the FFT.
