Алгоритм Фюрера

[vlad_light]

Хочу разобраться в алгоритме быстрого умножения, но что-то пока не очень получается
Вот ссылка на статью, по которой разбираюсь: http://www.mpi-inf.mpg.de/~csaha/intMult.pdf
Итак, алгоритм состоит из 5-ти частей:

• выбор параметров $M, m, k, c, p$. Тут почти всё понятно, кроме $c$. У них написано, что его можно взять равным $42$, хотя у меня получилось, что $c=O(\log N)$. Это я что-то не так посчитал или они имели ввиду, что для реальных чисел $42$ хватит с головой?
• кодирование чисел многочленами -- тут тоже всё просто
• вычисление корня $\rho (\alpha )$ -- просто подставить в формулу.
• преобразование Фурье -- об этом позже
• восстановление числа -- тоже по формуле

Теперь про преобразование Фурье. Вводится понятие групповой алгебры и характера:

(Оффтоп)

$E$ - аддитивная абелева группа, $\mathbb C$ - кольцо комплексных чисел. Тогда групповой алгеброй называется множество всевозможных сумм $\sum\limits _{g\in E}\alpha _gg, \alpha _g\in \mathbb C$ с операциями покоординатного сложения и "свёрточного" умножения.
Гомоморфизм $\chi :E\to\mathbb C^*$ называется характером. Образом характера является корень из 1. Множество всех характеров образуют мультипликативную группу $\hat E$, изоморфную $E$.

Далее вводятся непонятные для меня обозначения $|\chi \rangle =\sum\limits _{x\in E}\chi (x)|x\rangle$ и $\langle \chi |f\rangle ,f\in \mathbb C[E], \chi\in\hat E$. И ещё не понятно, как в явном виде найти все характеры (группу $\hat E$)?
Заранее спасибо за помощь!

[g______d]

vlad_light в сообщении #715980 писал(а):

И ещё не понятно, как в явном виде найти все характеры (группу $\hat E$)?

Например, разложить группу в прямое произведение циклических. Любой характер однозначно задается своими значениями на образующих этих циклических компонент. Отсюда же видно, что группа характеров изоморфна исходной группе.

-- 26.04.2013, 22:12 --

vlad_light в сообщении #715980 писал(а):

Далее вводятся непонятные для меня обозначения $|\chi \rangle =\sum\limits _{x\in E}\chi (x)|x\rangle$

Это элемент групповой алгебры, у которого $\alpha_g=\chi(g)$.

[Xaositect]

vlad_light в сообщении #715980 писал(а):

Это я что-то не так посчитал или они имели ввиду, что для реальных чисел хватит с головой?

Ограниченность $c$ следует из того, что $p$ достаточно большое ($p$ равно $1$ по модулю $2M$, значит $p\geqslant 2M+1$)

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