Произведение многочленов над Z_2 через СФЭ

[Zurabman]

Доброго времени суток всем!

Для решения моей задачи необходимо сделать одну из таких вещей:
Два многочлена степени $n-1$ над $\mathbb{Z}_2$. Представить их произведение через схему из функциональных элементов.
Переменные, подающиеся на вход СФЭ - просто коэффициенты многочленов.
Соответственно на выходе будет $2n$ переменных. И они будут задавать многочлен степени $2n$.
Задача состоит в том, чтобы глубина схемы была $O(\log(n))$. Соответственно, здесь надо как-то прикрутить в эту схему деревья Уоллеса.

Мои попытки решения.
Вручную расписал что будет, если перемножить два многочлена.
Соответственно пусть $a_0 + a_1x + ... a_{n}x^{n}$ и $b_0 + b_1x + ... b_{n}x^{n}$ - перемножаемые многочлены. Далее, пусть $c_0+c_1x+...+c_{2n}x^{2n}$ - полученный многочлен-произведение. Далее, я получил , что $c_i=\sum\limits_{k+l=i}a_kb_l$.
Собственно говоря, алгебраическое выражение есть (просьба на всякий случай проверить). Теперь, как это реализовать через СФЭ и при том, чтобы глубина схемы была $O(\log(n))$, как указано выше.
Интересная мысль - так как всё над $\mathbb{Z}_2$, то возможно тут можно местами умножение заменить на коньюнкцию. И как дальше использовать деревья Уоллеса? На каком этапе? (Их использование как раз поможет дать логарифмическую глубину)

Сам пробую и начинаю путаться.

Заранее спасибо!

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Zurabman
Приведите попытки решения задачи, укажите конкретные затруднения
Наберите все формулы и термы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Вернул

[Xaositect]

Zurabman в сообщении #785923 писал(а):

Интересная мысль - так как всё над $\mathbb{Z}_2$, то возможно тут можно местами умножение заменить на коньюнкцию

Умножение в $\mathbb{Z}_2$ --- это и есть конъюнкция. Можно заменить его везде :)

Дерево, конечно, нужно, но не дерево Уоллеса, а все значительно проще. Переносов никаких нет, все коэффициенты занимают один бит, никаких сложностей. Вот, скажем, есть $n$ элементов $a_1,\dots,a_n\in \mathbb{Z}_2$. Как построить схему, которая вычисляет $a_1 + a_2 + \dots + a_n$ в $\mathbb{Z}_2$?

[vlad_light]

(Оффтоп)

Цитата:

Как построить схему, которая вычисляет $a_1 + a_2 + \dots + a_n$ в $\mathbb{Z}_2$?

При $n\leq 8$ на языке си это выглядит так:

sum = (((a * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

т.е. за $O(1)$ операций.
http://www-graphics.stanford.edu/~seander/bithacks.html