Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
1.5.2. Алгоритм Винограда с использованием ТЧП
Теоретико-числовые преобразования (см. 1.4.7) могут быть использованы для эффективного вычисления круговой свертки в алгоритме Винограда. В [1.14, 1.15] предлагается так называемый гибридный алгоритм с использованием ТЧП Мерсенна (см. 1.4.6). В табл. 1.7 приведено число требуемых арифметических операций для где — простое; . В этом случае ДПФ сводится к вычислению -точечной круговой свертки, которую, в свою очередь, можно представить в виде прямого произведения и -точечных сверток (см. 1.4.7). Для вычисления -точечной свертки используется ТЧП Мерсенна, требующее операций умножения и сложения.
где 
— простое; 
. В этом случае ДПФ сводится к вычислению 
-точечной круговой свертки, которую, в свою очередь, можно представить в виде прямого произведения 
и 
-точечных сверток (см. 1.4.7). Для вычисления 
-точечной свертки используется ТЧП Мерсенна, требующее 
операций умножения и 
сложения.