Выразить операцию сложения

[Профессор Снэйп]

Дано $F = \mathbb{Z}_2^k$. На $F$ задан обычный побитовый $\mathbf{xor}$ и умножение, так, что умножение вместе с этим ксором, рассматриваемым как сложение, задаёт на $F$ структуру поля Галуа. Теперь начинаем мыслить об элементах $F$ как о двоичных записях натуральных чисел от $0$ до $2^k - 1$. Можно ли выразить сложение таких чисел по модулю $2^k$ через полевые операции?

В выражении (если оно, конечно, существует, в чём я не уверен, хотя не уверен и в обратном) можно использовать $\mathbf{xor}$, умножение (которое в поле), константы $\mathbf{0}$, $\mathbf{1}$ и $\mathbf{u}$, где ноль с единицей понятно что такое, а $\mathbf{u}$ - порождающая мультипликативной группы поля $F$. Для определённости будем считать $\mathbf{1} = (0, \ldots, 0, 1)$, $\mathbf{u}^s = (0, \ldots, 0, 1, 0, \ldots, 0)$, где $s < k$ и единственная единица в выражении для $\mathbf{u}^{s}$ стоит на $(s+1)$-ом месте, считая с правого края.

Замучился я с этим дурацким переносом разрядов!!! Но ведь как-то же в процессорах все эти штуки реализуют

[venco]

Профессор Снэйп в сообщении #610441 писал(а):

Замучился я с этим дурацким переносом разрядов!!! Но ведь как-то же в процессорах все эти штуки реализуют

В процессорах используют не xor, а not-and и/или not-or.

[Профессор Снэйп]

venco в сообщении #610469 писал(а):

Замучился я с этим дурацким переносом разрядов!!! Но ведь как-то же в процессорах все эти штуки реализуют

В процессорах используют не xor, а not-and и/или not-or.[/quote]
Охотно верю

Я про процессор не потому заговорил, что думаю, будто там пользуются именно ксором. Более того, я почти уверен, что поля Галуа туда не зашивают. Просто сказал про процессоры в некоем "собирательном" смысле: работают с битами, реализуют много разных вещей минимальным набором инструментов...

А задача эта меня давно волновала в связи с другой темой: про перестановки на абелевых группах. Там всё свелось к перестановкам на группах $\mathbb{Z}_{2^n} \times \mathbb{Z}_{2^m}$ и $\mathbb{Z}_{2^n} \times \mathbb{Z}_{2^m} \times \mathbb{Z}^{2^k}$, была идея для начала "уравнять" все биты в правах, задать перестановку как умножение на ненулевой неединичный элемент поля, а потом восстанавливать старую операцию сложения. Правда, так и не удалось понять, как это можно сделать и можно ли вообще.

Ну да чёрт с ними, с теми группами. Задача про выражение операций сама по себе интересна. Для маленьких $k$ выразить вроде бы получается. К примеру, при $k = 2$ можно взять

$$ x + y = x \mathop{\mathbf{xor}} y \mathop{\mathbf{xor}} \mathbf{u}(x \mathop{\mathbf{xor}} \mathbf{1})(x \mathop{\mathbf{xor}} \mathbf{u} \mathop{\mathbf{xor}} \mathbf{1}) (y \mathop{\mathbf{xor}} \mathbf{1})(y \mathop{\mathbf{xor}} \mathbf{u} \mathop{\mathbf{xor}} \mathbf{1}) $$

[arseniiv]

$x + y = s(x, y, P)$.

$P_0 = \mathbf 0$,
$P_{n + 1} = \mathbf u p(d_n(x), d_n(y), P_n)$.

$P = \mathop{\mathbf{xor}}_{i = 0}^{k - 1} P_i$.

$d_i(x)$ — выделенный $i$-й разряд $x$. Не совсем понимаю пока, как выражается.

$s$ и $p$ — функции [порязрядной суммы трёх чисел без учёта переносов] и [переносов суммы трёх чисел без сдвига] с таблицами истинности $01101001$ и $00010111$ в каждом разряде. Вообще не понимаю, как с таким умножением выражаются. Возможно, стоит сначала выразить порязрядное умножение, а потом эти через него.

Вы так же действовали для $k = 2$?

Попробую выразить себе поразрядное умножение и выделение разряда; и, надеюсь, не напутал.

-- Вс авг 26, 2012 00:40:33 --

(Боюсь, ничего практически здесь полезного не написал.)

-- Вс авг 26, 2012 01:08:25 --

А ведь поразрядное умножение реализуется через выделение разряда! Выделяем, сдвигаем, умножаем, сдвигаем назад, а потом всё ксорим.

[Профессор Снэйп]

arseniiv в сообщении #610517 писал(а):

Вы так же действовали для $k = 2$?

Для $k = 2$ я в явном виде выписал многочлен $f(x) = (x-1)(x-u+1)+1$, принимающий значения $1$ на числах $1$, $3$ (имеются в виду единица с тройкой при сложении по модулю $4$) и $0$ на остальных. И теперь, складывая числа $x$ и $y$, я их вначале складываю побитовым ксором, а если $f(x)f(y)$ оказывается равным единице, то дополнительно ксорю $1$ в старший разряд суммы.

При $k = 2$ больше ничего делать и не надо, поскольку более старших разрядов у нас уже и нет. А вот при бОльшем $k$ надо начинать учитывать дальнейшие переносы... Конечно, для каждого конкретного $k$ можно тупо перебирать все возможные значения слагаемых и наворачивать многочлены, осуществляющие особое сложение для каждой их пары. Но это плохой метод: всё равно что составлять специальные таблицы умножения двухзначных, трёхзначных и т. д. чисел вместо того, чтобы учиться умножать столбиком. И длины формул будут экспоненциально разрастаться с ростом $k$. Хуже того, я даже не вижу систему, которое бы позволила однородным образом выписывать такие длинные формулы, просто замечаю, что раз $F$ конечно, то там будет конечный перебор.

В идеале бы хотелось иметь одну и ту же формулу для всех достаточно больших $k$

-- Вс авг 26, 2012 01:51:16 --

arseniiv в сообщении #610517 писал(а):

А ведь поразрядное умножение реализуется через выделение разряда! Выделяем, сдвигаем, умножаем, сдвигаем назад, а потом всё ксорим.

Я это мыслю так: храним в уме бит переноса, движемся справа налево, на очередной позиции ксорим два имеющихся разряда и бит переноса к ним до кучи, если проксорили не менее двух единиц, кладём в бит переноса $1$, иначе кладём $0$, сдвигаемся влево на следующую позицию и повторяем процедуру, останавливаемся, когда доходим до левого края.