The Discrete Fourier Transform in Coding and Cryptography
James L. Massey · 1999
Some applications of the Discrete Fourier Transform #DFT# in coding and in cryptography are described. The DFT over general commutative rings is introduced and the condition for its existence given. Blahut's Theorem, which relates the DFT to linear complexity, is shown to hold unchanged in general commutative rings. I. The #Usual# Discrete Fourier Transform Let # be a primitive N th root of unity in a #eld F , i.e., # N = 1 but # i 6= 1 for 1 # i#N. The #usual# Discrete Fourier Transform #DFT# of length N generated by # is the mapping DFT # ### from F N to F N de#ned by B =DFT # #b# in the manner B#i#= N,1 X n=0 b#n## in #1# where b =#b#0#;b#1#; ...b#N , 1## is the #time-domain" sequence and B =#B#0#;B#1#; ...B#N , 1## is the #frequencydomain " sequence. As is very well known, the inverse transform is given by b#n#= 1 N N,1 X i=0 B#i## ,in #2# where N denotes the sum of N 1's in the #eld F . II. The DFT in Coding Coding applications of the DFT rely on the ...