Immagina di comprendere un algoritmo così bene da poterlo eseguire - a mano - a memoria - e senza memorizzare trucchi innaturali Il ZK Book si è ampliato di nuovo, questa volta per insegnare la Trasformata di Fourier Veloce -- specificamente la Trasformata Teoretica dei Numeri (NTT). L'algoritmo NTT valuta un polinomio in n punti in O(n log n) tempo. Normalmente, tale valutazione richiederebbe O(n²) tempo. Sebbene la Trasformata di Fourier Veloce abbia già numerose risorse di apprendimento, le abbiamo trovate insoddisfacenti. Ad esempio, una spiegazione molto comune si basa su "dividere il polinomio in termini pari e dispari," utilizzando "fattori di twiddle" e "farfalle." Tuttavia, questi metodi sembrano scoperte casuali fortunate che descrivono l'algoritmo piuttosto che spiegarlo. Consideriamo tali caratteristiche elencate sopra come incidentali a concetti sottostanti più profondi -- e molto più facili da comprendere. Siamo persino arrivati a evitare analogie con i numeri complessi. Abbiamo prestato grande attenzione per garantire che ogni passo del percorso di apprendimento sia motivato e che ogni passo sia un'estensione banale del precedente. Pertanto, non ci sono salti concettuali o scoperte sorprendenti. Non lasciare che i nomi dei capitoli ti spaventino; i principi sottostanti sono solo algebra di base. Entro la fine dei 13 capitoli, sarai in grado di calcolare la Trasformata Teoretica dei Numeri a mano! Link successivo.