Talk:Discrete Fourier transform over a ring

The article "Number-theoretic transform" has been merged into this article: See old talk-page here. Selinger (talk) 01:58, 24 June 2011 (UTC)

Here is my rationale for creating this article:

• somewhere we need a description of the discrete Fourier transform over any field. This is used, for example, in Reed-Solomon codes.
• the existing main article on the discrete Fourier transform is primarily over the complex numbers (although other fields are briefly mentioned). I think this should stay as it is, because most people who need the DFT only need the complex case, the the added generality of field theory would benefit very few people. Talk:discrete Fourier transform already contains complaints that the content is too abstract.

I also propose that the existing page on the number theoretic transform be merged into this (actually, it should be deleted and redirected here). That page is already in bad shape, and the content is entirely subsumed by this new article.

Selinger (talk) 23:50, 14 March 2008 (UTC)

I have merged in the page on Discrete weighted transform (suggested for two years with no complaints). --Qetuth (talk) 06:47, 21 December 2011 (UTC)

Requirements for convolution theorem with composite moduli

Regarding this statement:

For the number theoretic transform to work in a useful way when the modulus is composite (for the inverse algorithm, convolution etc. to work), it suffices that the modulus is chosen so that a primitive root of order $n$ exists (where $n$ is the transform length), and such that the multiplicative inverse of $n$ exists. Note that if $\alpha$ is a primitive root of order $n$, then $\alpha$ is automatically invertible with inverse $\alpha ^{n-1}$.

I was doing an experiment and when I computed IDFT(DFT([1,0,0,0,0,0,0,0])) in the integers mod 85 using 2 as my primitive 8th root mod 85, the result is [1, 0, 0, 0, 51, 0, 0, 0], not [1,0,0,0,0,0,0,0] as expected (and 8 has an inverse mod 85, 32). Eventually I figured out the problem: 2⁴=16, and 16-1 = 15 is not invertible mod 85, so you can't divide by β-1 in the proof. So a sufficient condition would be: $\alpha ^{k}-1$ is invertible for all 0 < k < n (I'm uncertain if this condition is necessary). This obviously applies with prime moduli, but I haven't figured out if it applies with Fermat/Mersenne numbers. Am I correct, and if so, where should I find a reference to back this up? Thanks! Dcoetzee 06:53, 14 December 2011 (UTC)

I found a source and fixed this by generalising the entire article to discuss rings rather than fields. The desired condition to make this work was that $\alpha$ is a principal nth root of unity. Dcoetzee 05:43, 22 December 2011 (UTC)

Typo in polynomial formulation

Final line: what is q? Should be subscripted p?