Продукт без ручной клади

редактировать

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

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

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

Содержание

1 Определение
2 Пример
3 Умножение многочленов
4 Приложения
5 Реализации
6 Другие базы
7 См. Также
8 Ссылки

Определение

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

ci = ⨁ j = 0 iajbi - j {\ displaystyle c_ {i} = \ bigoplus _ {j = 0} ^ {i} a_ {j} b_ {ij}}

{\ displaystyle c_ {i} = \ bigoplus _ { j = 0} ^ {i} a_ {j} b_ {ij}}

Пример

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

1 0 1 0 0 0 1 0 = а --------------- | --- | ------- | - 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 2. Для каждого бита, установленного в числе a, число b сдвигается влево на столько битов, сколько указано положением бита в a. Все эти сдвинутые версии затем объединяются с использованием исключающего или вместо обычного сложения, которое использовалось бы для обычного длинного умножения. Это можно увидеть в столбцах, обозначенных ^, где обычное добавление приведет к переносу в столбец слева, чего здесь не происходит.

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

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

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

A = ∑ iai X i = X 7 + X 5 + X 1 B = ∑ ibi X i = X 7 + X 4 + Икс 2 + Икс 1 {\ displaystyle 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}}

{\ displaystyle 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 ⋅ В знак равно ∑ ici Икс я знак равно Икс 14 + Икс 12 + Икс 11 + Икс 7 + Икс 6 + Икс 5 + Икс 3 + Икс 2 {\ displaystyle 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}}

{\ displaystyle 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. Обратите внимание, как $(Икс 7 ⋅ Икс 1) + (Икс 1 ⋅ Икс 7) ≡ 0 {\ displaystyle (X ^ {7} \ cdot X ^ {1}) + (X ^ {1} \ cdot X ^ {7}) \ Equiv 0}$ ${\ displaystyle (X ^ {7} \ cdot X ^ {1}) + (X ^ {1} \ cdot X ^ {7}) \ эквив 0}$ и $(X 7 ⋅ X 2) + (X 5 ⋅ X 4) ≡ 0 {\ displaystyle (X ^ {7} \ cdot X ^ {2 }) + (X ^ {5} \ cdot X ^ {4}) \ Equiv 0}$ ${\ displaystyle (X ^ {7} \ cdot X ^ {2}) + (X ^ {5} \ cdot X ^ {4}) \ Equiv 0}$ благодаря арифметике в GF (2). Это соответствует столбцам, помеченным ^в примере.

Приложения

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

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

Реализации

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

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

Другие базисы

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

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

См. Также

Ссылки