Imaginați-vă că înțelegeți un algoritm atât de bine încât îl puteți realiza - manual - de pe vârful capului - și fără a memora trucuri nenaturale Cartea ZK s-a extins din nou, de data aceasta pentru a învăța transformata rapidă Fourier - în special transformata teoretică a numerelor (NTT). Algoritmul NTT evaluează un polinom pe n puncte în timp O(n log n). În mod normal, o astfel de evaluare ar dura O(n²) timp. Deși transformata rapidă Fourier are deja numeroase resurse de învățare, ni s-au părut nesatisfăcătoare. De exemplu, o explicație foarte comună se bazează pe "împărțirea polinomului în termeni pari și impari", folosind "factori twiddle" și "fluturi". Cu toate acestea, aceste metode apar ca descoperiri aleatorii întâmplătoare care descriu algoritmul mai degrabă decât să-l explice. Considerăm că astfel de caracteristici enumerate mai sus sunt incidentale conceptelor de bază mai profunde și mult mai ușor de înțeles. Mergem chiar atât de departe încât să evităm analogiile cu numerele complexe. Am avut mare grijă să ne asigurăm că fiecare pas al călătoriei de învățare este motivat și că fiecare pas este o extensie banală a precedentului. Prin urmare, nu există salturi conceptuale sau descoperiri surpriză. Nu lăsa numele capitolelor să te sperie; Principiile de bază sunt doar algebra de bază. Până la sfârșitul celor 13 capitole, veți putea calcula manual transformarea teoretică a numerelor! Link următor.