Хочу разобраться в алгоритме быстрого умножения, но что-то пока не очень получается
Вот ссылка на статью, по которой разбираюсь:
http://www.mpi-inf.mpg.de/~csaha/intMult.pdfИтак, алгоритм состоит из 5-ти частей:
- выбор параметров
. Тут почти всё понятно, кроме
. У них написано, что его можно взять равным
, хотя у меня получилось, что
. Это я что-то не так посчитал или они имели ввиду, что для реальных чисел
хватит с головой? - кодирование чисел многочленами -- тут тоже всё просто
- вычисление корня
-- просто подставить в формулу. - преобразование Фурье -- об этом позже
- восстановление числа -- тоже по формуле
Теперь про преобразование Фурье. Вводится понятие групповой алгебры и характера:
(Оффтоп)

- аддитивная абелева группа,

- кольцо комплексных чисел. Тогда групповой алгеброй называется множество всевозможных сумм

с операциями покоординатного сложения и "свёрточного" умножения.
Гомоморфизм

называется характером. Образом характера является корень из 1. Множество всех характеров образуют мультипликативную группу

, изоморфную

.
Далее вводятся непонятные для меня обозначения

и
![$\langle \chi |f\rangle ,f\in \mathbb C[E], \chi\in\hat E$ $\langle \chi |f\rangle ,f\in \mathbb C[E], \chi\in\hat E$](https://dxdy-04.korotkov.co.uk/f/3/0/5/3052eb12a83875397a8c90ca2cdd492e82.png)
. И ещё не понятно, как в явном виде найти все характеры (группу

)?
Заранее спасибо за помощь!