Exemple de calcul de FFT

Exemple qvec n = 8 sur les entiers modulo 257 On prend w = 4 qui est racine 8-ieme de l'unite

P = 1
1 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
P = x^1
0 1 0 0 0 0 0 0
1 4 16 64 256 253 241 193
P = x^2
0 0 1 0 0 0 0 0
1 16 256 241 1 16 256 241
P = x^3
0 0 0 1 0 0 0 0
1 64 241 4 256 193 16 253
P = x^4
0 0 0 0 1 0 0 0
1 256 1 256 1 256 1 256
P = x^5
0 0 0 0 0 1 0 0
1 253 16 193 256 4 241 64
P = x^6
0 0 0 0 0 0 1 0
1 241 256 16 1 241 256 16
P = x^7
0 0 0 0 0 0 0 1
1 193 241 253 256 64 16 4
255 8 0 226 37 240 3 0
255 85 127 200 78 255 194 75