Aufgabe 12: (Fouriertransformation)
Programmieren Sie das Verfahren der Schnellen Fouriertransformation (FFT).
Testen Sie ihr Programm, indem Sie im Körper der komplexen Zahlen den Vektor [1 2 3 4 5 6 7 8] transformieren und mit der inversen Fouriertransformation wieder zurücktransformieren.
Testen Sie ihr Programm, indem Sie im Körper ℤ17 der ganzen Zahlen modulo 17 den Vektor [1 2 3 4 5 6 7 8] transformieren und mit der inversen Fouriertransformation wieder zurücktransformieren. Importieren Sie zuvor die Klasse ModInt, damit Sie mit den Elementen von ℤ17 rechnen können.