CUDA integer FFTs

[jasonp]

Originally Posted by jasonp

I can also provide non-power-of-two transforms that use the Winograd algorithm. How can we go about finding non-power-of-two roots of 2 by e.g. augmenting the iterated Tonelli-Shanks approach? Would that multiply the number of such roots available?

To jot this down for posterity, the answer to this is embarrassingly simple: to find an Nth root of two modulo p where N>2, just find the roots (if any) of x^N-2 in the field of polynomials with coefficients modulo p. I've been using Cantor-Zassenhaus code for years that does this, and never made the connection.

For the sake of completeness, here are the 32-bit primes that allow a DWT of largest size when including powers of 3,5,7:

p 2118090241 primroot 13 factors 2 2 2 2 2 2 2 2 2 3 3 5 7 23 571 dwt-root 348785556 order 80640 : 2 2 2 2 2 2 2 2 3 3 5 7
p 2247843151 primroot 13 factors 2 3 3 3 3 5 5 7 7 47 241 dwt-root 969636289 order 198450 : 2 3 3 3 3 5 5 7 7
p 2273745601 primroot 47 factors 2 2 2 2 2 2 3 3 3 5 5 7 73 103 dwt-root 1801095565 order 302400 : 2 2 2 2 2 2 3 3 3 5 5 7
p 2683625473 primroot 15 factors 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 11 1103 dwt-root 1165668607 order 221184 : 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3
p 2913750001 primroot 11 factors 2 2 2 2 3 3 5 5 5 5 5 5 5 7 37 dwt-root 2357374036 order 112500 : 2 2 3 3 5 5 5 5 5
p 2927769601 primroot 59 factors 2 2 2 2 2 2 2 2 2 2 2 3 5 5 7 7 389 dwt-root 2873724403 order 188160 : 2 2 2 2 2 2 2 2 3 5 7 7
p 2990991361 primroot 19 factors 2 2 2 2 2 2 2 2 2 2 2 3 5 7 7 1987 dwt-root 1020298203 order 150528 : 2 2 2 2 2 2 2 2 2 2 3 7 7
p 3275037361 primroot 13 factors 2 2 2 2 3 3 3 3 3 5 7 41 587 dwt-root 2866099729 order 136080 : 2 2 2 2 3 3 3 3 3 5 7