6.26.3  La transformée de Fourier rapide : fft

fft a comme argument une liste (ou une séquence) [a₀,..a_N-1] où N est une puissance de deux.
fft renvoie la liste [b₀,..b_N-1] tel que pour k=0..N-1 on ait :
fft([a₀,..a_N-1])[k]=b_k=∑_j=0^N-1x_jω_N^{-k· j} avec ω_N racine N-ième de l’unité.
On tape :

On obtient :

On peut aussi travailler sur un corps fini ℤ/pℤ, en indiquant une racine N-ième primitive de l’unité en 2ième argument et p en 3ième argument de fft. Par exemple on verifie que 22798 est une racine primitive d’ordre 128 de 1 modulo 35969. Par exemple, calculons par FFT le carré d’un polynôme à coefficients entiers aléatoire inférieur à 10, de degré 60, représenté par la liste de ses coefficients par ordre croissant complété par des 0 pour avoir une liste de taille N=128 :

il suffit maintenant de calculer le produit terme à terme de p avec lui-même et d’en calculer la FFT inverse