Товар без переноски

Вычисление продукта без переноса.

Произведение без переноса двух двоичных чисел является результатом без переноса умножения этих чисел . Эта операция концептуально работает как длинное умножение. за исключением того, что перенос отбрасывается, а не применяется к более значимой позиции. Его можно использовать для моделирования операций над конечными полями . в частности умножение полиномов из GF(2)[ X ], кольцо полиномов над GF(2) .

Эта операция также известна как умножение XOR , поскольку сложение с отбрасыванием переноса эквивалентно исключающему или.

Определение

Даны два числа $\textstyle a=\sum _{i}a_{i}2^{i}$ и $\textstyle b=\sum _{i}b_{i}2^{i}$, с $a_{i},b_{i}\in \{0,1\}$ обозначающие биты этих чисел. Тогда произведение этих двух чисел без переноса определяется как $\textstyle c=\sum _{i}c_{i}2^{i}$, с каждым битом $c_{i}$ вычисленный как исключающее или произведение битов входных чисел следующим образом:

$c_{i}=\bigoplus _{j=0}^{i}a_{j}b_{i-j}$

Пример

Рассмотрим a = 10100010 ₂ и b = 10010110 ₂ , со всеми числами, заданными в двоичном формате. Тогда их умножение без переноса — это, по сути, то, что можно было бы получить от выполнения длинного умножения, но игнорирования переносов.

                  1 0 1 0 0 0 1 0 = a
   ---------------|---|-------|--
   1 0 0 1 0 1 1 0|0 0 0 0 0 0 0
       1 0 0 1 0 1 1 0|0 0 0 0 0
               1 0 0 1 0 1 1 0|0
   ------------------------------
   1 0 1 1 0 0 0 1 1 1 0 1 1 0 0
             ^ ^

Таким образом, произведение a и b без переноса будет равно c = 101100011101100 ₂ . Для каждого бита, установленного в числе a , число b сдвигается влево. столько бит, сколько указано позицией бита в файле . Все эти смещенные версии затем объединяются с использованием исключающего или, вместо обычного сложения, которое использовалось бы для обычного длинного умножения. Это можно увидеть в столбцах, обозначенных ^, где регулярное сложение приведет к переносу в столбец слева, чего здесь не происходит.

Умножение многочленов

Произведение без переноса также можно рассматривать как умножение полиномов. над полем GF(2) . Это потому, что эксклюзив или соответствует дополнению в этом поле.

В приведенном выше примере числа a и b соответствуют полиномам.

$A=\sum _{i}a_{i}X^{i}=X^{7}+X^{5}+X^{1}\qquad B=\sum _{i}b_{i}X^{i}=X^{7}+X^{4}+X^{2}+X^{1}$

и продукт их

$C=A\cdot B=\sum _{i}c_{i}X^{i}=X^{14}+X^{12}+X^{11}+X^{7}+X^{6}+X^{5}+X^{3}+X^{2}$

что и кодирует вычисленное выше число c . Обратите внимание, как $(X^{7}\cdot X^{1})+(X^{1}\cdot X^{7})\equiv 0$ и $(X^{7}\cdot X^{2})+(X^{5}\cdot X^{4})\equiv 0$ благодаря арифметика в GF(2). Это соответствует столбцам, отмеченным ^ в примере.

Приложения

Элементы GF(2 ^н ), т.е. конечное поле , порядок которого равен степени двойки , обычно представляются в виде полиномов в GF(2)[ X ]. Умножение двух таких элементов поля состоит из умножения соответствующих многочленов, с последующей редукцией по некоторому неприводимому многочлену который взят из конструкции поля. Если полиномы закодированы как двоичные числа, Умножение без переноса можно использовать для выполнения первого шага этого вычисления.

Такие поля находят применение в криптографии и некоторых алгоритмах контрольных сумм .

Реализации

Последние процессоры x86 поддерживают набор инструкций CLMUL и, таким образом, предоставляют аппаратную инструкцию для выполнения этой операции.

Это также часть RISC-V Bit-Manipulation ISA-расширения Zbc: умножение без переноса.

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

Другие базы

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

Полиномы над другими конечными полями простого порядка имеют приложения: но рассматривать коэффициенты такого многочлена как цифры одного числа довольно редко, поэтому умножение таких полиномов не будет рассматриваться как умножение чисел без переноса.

См. также

• Набор инструкций CLMUL , ISA x86. расширение
• Арифметика конечных полей
• Галуа/Режим счетчика