Kuvittele, että ymmärrät algoritmin niin hyvin, että voit suorittaa sen -käsin - pään päältä - ja muistamatta luonnottomia temppuja ZK-kirja on jälleen laajentunut, tällä kertaa opettamaan nopeaa Fourier-muunnosta - erityisesti numeroteoreettista muunnosta (NTT). NTT-algoritmi arvioi polynomin n pisteessä O(n log n) ajassa. Normaalisti tällainen arviointi veisi O(n²) aikaa. Vaikka nopeassa Fourier-muunnoksessa on jo lukuisia oppimisresursseja, ne eivät mielestämme olleet tyydyttäviä. Esimerkiksi hyvin yleinen selitys perustuu "polynomin jakamiseen parillisiin ja parittomiin termeihin", käyttämällä "pyöriviä tekijöitä" ja "perhosia". Nämä menetelmät vaikuttavat kuitenkin sattumanvaraisilta satunnaisilta löydöiltä, jotka kuvaavat algoritmia sen sijaan, että selittäisivät sitä. Katsomme, että yllä luetellut piirteet ovat satunnaisia syvemmille - ja paljon helpommin ymmärrettäville - taustalla oleville käsitteille. Menemme jopa niin pitkälle, että vältämme analogioita kompleksilukuihin. Pidimme huolta siitä, että oppimismatkan jokainen vaihe on motivoitunut ja että jokainen askel on triviaali jatke edelliselle. Siksi käsitteellisiä harppauksia tai yllätyksiä ei ole. Älä anna lukujen nimien pelotella sinua; Taustalla olevat periaatteet ovat vain perusalgebraa. 13 luvun loppuun mennessä pystyt laskemaan lukuteoreettisen muunnoksen käsin! Linkki seuraavaksi.