доктор физико-математических наук, профессор
doctor of science, professor
кандидат физико-математических наук; начальник лаборатории
candidate of science; head of laboratory
В работе предпринимается обзор современного состояния теории быстрых алгоритмов умножения чисел и многочленов. Рассматривается процесс эволюции методов умножения от первых блочных алгоритмов Карацубы и Тоома 1960-х гг. к методам 1970-х гг., опирающимся на дискретное преобразование Фурье (ДПФ), и далее к новейшим методам, разработанным в 2007–2019 гг. Современные методы умножения сочетают использование специальных алгебраических структур, переход к приближенным вычислениям, особые формы преобразований Фурье: многомерное ДПФ, аддитивный аналог ДПФ. Эти и другие существенные для быстрых методов умножения концепции подробно рассматриваются в настоящем обзоре. Отдельно предусмотрено введение в теорию ДПФ с извлечением необходимых для изложения материала фактов. В заключительной части обзора приводятся краткие сведения о результатах в области параллельных алгоритмов умножения, аккуратных оценок сложности базовых методов умножения, алгоритмов умножения в реальном времени, мультипликативной сложности умножения многочленов над конечными полями. Отмечены модели вычислений, в которых умножение имеет линейную или квадратичную сложность.
The paper provides a survey of the modern state of the theory of fast multiplication ofnumbers and polynomials. We consider the development of multiplication methods from theinitial block algorithms of 1960s due to Karatsuba and Toom to the methods of 1970s basedon the Discrete Fourier transform (DFT) and further to the novel methods invented in 2007–2009. Modern multiplication methods combine exploiting of special algebraic structures, the useof approximate computations, special forms of Fourier transforms, namely, multidimensionalDFT, additive analogue of DFT. These and other concepts essential for the fast multiplicationalgorithms are thoroughly discussed in the present survey. In particular, we provide anintroduction to the theory of DFT with derivation of facts necessary for the exposition.The final part of the survey contains a brief discussion of results on parallel multiplicationalgorithms, accurate complexity bounds of the basic methods, online multiplication algorithms,multiplicative complexity of the multiplication of polynomials over finite fields. We mentioncomputational models where multiplication has either linear, or quadratic complexity.
The authors declare that there are no conflicts of interest present.