Представьте себе, что вы понимаете алгоритм так хорошо, что можете выполнить его - вручную - наизусть - и без запоминания каких-либо неестественных трюков Книга ZK снова расширилась, на этот раз, чтобы научить Быстрому Преобразованию Фурье — в частности, Преобразованию Числовой Теории (NTT). Алгоритм NTT оценивает многочлен в n точках за O(n log n) времени. Обычно такая оценка занимает O(n²) времени. Хотя Быстрое Преобразование Фурье уже имеет множество учебных ресурсов, мы нашли их неудовлетворительными. Например, очень распространенное объяснение основывается на "разделении многочлена на четные и нечетные члены," используя "факторы твиддла" и "бабочки." Однако эти методы выглядят как случайные удачные открытия, которые описывают алгоритм, а не объясняют его. Мы считаем такие особенности, перечисленные выше, случайными по отношению к более глубоким — и гораздо более понятным — основным концепциям. Мы даже стараемся избегать аналогий с комплексными числами. Мы тщательно позаботились о том, чтобы каждый шаг учебного пути был обоснован, и чтобы каждый шаг был тривиальным продолжением предыдущего. Поэтому нет концептуальных скачков или неожиданных открытий. Не позволяйте названиям глав пугать вас; основные принципы — это просто базовая алгебра. К концу 13 глав вы сможете вычислить Преобразование Числовой Теории вручную! Ссылка далее.