Аннотация:Быстрые алгоритмы вычисления преобразования Фурье, возникли в связи с
проблемами ускорения обработки и передачи информации, но оказались весьма
полезными в связи с созданием более эффективных алгоритмов умножения больших натуральных чисел и многочленов - важной проблеме в теории алгоритмов,
теории чисел и алгебре. В 1962г. А.А. Карацуба предложил быстрый рекурсивный
алгоритм умножения целых чисел. В 1965г. Кули и Тьюки опубликовали быстрый алгоритм
вычисления комплексного преобразования Фурье и, хотя речь в этой работе не шла
об умножении целых чисел, все последующие ускорения алгоритмов умножения
были связаны с использованием различных вариантов быстрого преобразования
Фурье. Две упомянутые работы имели прорывной характер и породили большое
направление исследований по быстрым алгоритмам умножения. Подробный обзор развития
этой области можно найти в обстоятельной работе С.Б. Гашкова и И.С. Сергеева. Отметим здесь лишь основные достижения, опубликованные в работах А.Шёнхаге и Ф.Штрассен (1971), М.Фюрера (2007). В 2008г. А. Де +3 соавтора, нашли алгоритм такой же сложности, как и у М.Фюрера, но использующий вместо поля комплексных чисел некоторое конечное кольцо. Наконец, в 2019г. в работе Д. Харви и ван дер Хоевена, был опубликован алгоритм умножения целых чисел, имеющий сложность O(NlnN) арифметических операций. Существование такого алгоритма было предсказано ещё А.Шёнхаге и Ф.Штрассеном. По-видимому это окончательный результат. В дипломной работе А.Н. Костромина описывается и обосновывается быстрый алгоритм вычисления преобразования Фурье над конечными кольцами со специальными свойствами, не использующий рекурсию. В чём то он похож на алгоритм Кули и Тьюки.