Hãy tưởng tượng bạn hiểu một thuật toán đến mức bạn có thể thực hiện nó - bằng tay - từ trí nhớ - và không cần ghi nhớ bất kỳ mẹo nào không tự nhiên Cuốn sách ZK đã mở rộng thêm một lần nữa, lần này để dạy về Biến đổi Fourier nhanh -- cụ thể là Biến đổi lý thuyết số (NTT). Thuật toán NTT đánh giá một đa thức tại n điểm trong thời gian O(n log n). Thông thường, một đánh giá như vậy sẽ mất O(n²) thời gian. Mặc dù Biến đổi Fourier nhanh đã có nhiều tài nguyên học tập, nhưng chúng tôi thấy chúng không thỏa mãn. Ví dụ, một lời giải thích rất phổ biến dựa vào "chia đa thức thành các hạng chẵn và lẻ," sử dụng "các yếu tố twiddle," và "bướm." Tuy nhiên, những phương pháp này dường như là những phát hiện ngẫu nhiên may mắn mô tả thuật toán hơn là giải thích nó. Chúng tôi coi những đặc điểm như vậy được liệt kê ở trên là phụ thuộc vào những khái niệm sâu sắc hơn -- và dễ hiểu hơn nhiều. Chúng tôi thậm chí còn tránh sử dụng các phép ẩn dụ liên quan đến số phức. Chúng tôi đã rất cẩn thận để đảm bảo rằng mỗi bước trong hành trình học tập đều có động lực và rằng mỗi bước là một sự mở rộng tầm thường của bước trước đó. Do đó, không có những bước nhảy khái niệm hay phát hiện bất ngờ. Đừng để các tên chương làm bạn sợ hãi; các nguyên tắc cơ bản chỉ là đại số cơ bản. Vào cuối 13 chương, bạn sẽ có thể tính toán Biến đổi lý thuyết số bằng tay! Liên kết tiếp theo.