Discrete Fourier Transform of a shift of a tuple over a finite field

127 Views Asked by At

Let $a = a_0 a_1 \cdots a_{N-1}$ be a sequence over a finite field $\mathbb{F}_q$, where $N \mid q^n-1$ for some $n$. Let $\xi_N$ be a primitive $N$-th root of unity in the extension $\mathbb{F}_{q^n}$. Suppose we know a Discrete Fourier Transform (DFT) of $a$, given by $$ A_i = \sum_{j=0}^{N-1} a_j \xi_N^{ij}. $$ Fix $u$ with $0 \leq u \leq N-1$. What is the DFT of the sequence $(a_{j+u \pmod{N}})_{j=0}^{N-1}$? That is, can we write the DFT of the shifted sequence in terms of the DFT of the original? Thank you.