carry-less product

Given two numbers $\backslash textstyle\; a=\backslash sum\_i\; a\_i2^i$ and $\backslash textstyle\; b=\backslash sum\_i\; b\_i2^i$, with $a\_i,b\_i\backslash in\backslash \{0,1\backslash \}$ denoting the bits of these numbers, the carry-less product of these two numbers is defined to be $\backslash textstyle\; c=\backslash sum\_i\; c\_i2^i$, with each bit $c\_i$ computed as the exclusive or of products of bits from the input numbers as follows:{{cite web|url=http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode/|title=Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode - Rev 2|publisher=Intel|author=Shay Gueron|date=2011-04-13}}

: $c\_i=\backslash bigoplus\_\{j=0\}^i\; a\_jb\_\{i-j\}$

Consider a = 10100010₂ and b = 10010110₂,

with all numbers given in binary.

Then the carry-less multiplication of these is essentially what one would get

from performing a long multiplication but ignoring the carries.

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

^ ^

For every logic 1 bit in the number a, the number b is shifted to the left

as many bits as indicated by the position these bits a.

All these shifted versions are then "added" by using an XOR instead of the regular binary addition used in regular long multiplication.

Results of XOR are indicated by ^ . In full binary adder these would result in a carry to the column to the left. Here this does not happen so the carry-less product of a and b would be c = 101100011101100₂.

The carry-less product can also be seen as a multiplication of polynomials over the field GF(2). This is because the exclusive or corresponds to the addition in this field.

In the example above, the numbers a and b correspond to polynomials

: $A=\backslash sum\_i\; a\_i\; X^i=X^7+X^5+X^1\backslash qquad\; B=\backslash sum\_i\; b\_i\; X^i=X^7+X^4+X^2+X^1$

and the product of these is

: $C=A\backslash cdot\; B=\backslash sum\_i\; c\_i\; X^i=X^\{14\}+X^\{12\}+X^\{11\}+X^7+X^6+X^5+X^3+X^2$

which is what the number c computed above encodes. Notice how $(X^7\backslash cdot\; X^1)+(X^1\backslash cdot\; X^7)\backslash equiv0$ and $(X^7\backslash cdot\; X^2)+(X^5\backslash cdot\; X^4)\backslash equiv0$ thanks to the arithmetic in GF(2). This corresponds to the columns marked ^ in the example.

The elements of GF(2ⁿ), i.e. a finite field whose order is a power of two,

are usually represented as polynomials in GF(2)[X].

Multiplication of two such field elements

consists of multiplication of the corresponding polynomials,

followed by a reduction with respect to some irreducible polynomial

which is taken from the construction of the field.

If the polynomials are encoded as binary numbers,

carry-less multiplication can be used to perform the first step of this computation.

Such fields have applications in cryptography and for some checksum algorithms.

Recent x86 processors support the CLMUL instruction set and thus provide a hardware instruction to perform this operation.

It's also part of RISC-V Bit-Manipulation ISA-extensions Zbc: Carry-less multiplication.

For other targets it is possible to implement the computation above as a software algorithm,

and many cryptography libraries will contain an implementation

as part of their finite field arithmetic operations.

The definition of a carry-less product as the result of a long multiplication discarding carry

would readily apply to bases other than 2.

But the result depends on the basis, which is therefore an essential part of the operation.

As this operation is typically being used on computers operating in binary,

the binary form discussed above is the one employed in practice.

Polynomials over other finite fields of prime order do have applications,

but treating the coefficients of such a polynomial as the digits of a single number is rather uncommon,

so the multiplication of such polynomials would not be seen as a carry-less multiplication of numbers.

• CLMUL instruction set, an x86 ISA extension
• Finite field arithmetic
• Galois/Counter Mode

{{reflist}}

Category:Binary arithmetic

Category:Computer arithmetic

Category:Multiplication