Oh cool, I've never looked at the DFT in finite fields before. Looking at it from the DFT perspective, it means that we can compute the inverse DFT directly without having to invert the matrix.
The inverse DFT is given by N^(-1) * {{a^(- i * j)}},
and since we work in the finite field over 127, the negative exponent is resolved
by modular inverse in 127:
ModInverse(N, 127) * {{ModInverse(2^(i * j), 127)}}
i,j are the matrix indices from 0 to N-1.
Here N=7 and ModInverse(7, 127) = 105 for example.
That makes computing the inverse for any such invertible problem much easier!
|