Carry-less product

The carry-less product of two binary numbers is the result of carry-less multiplication of these numbers. This operation conceptually works like long multiplication except for the fact that the carry is discarded instead of applied to the more significant position. It can be used to model operations over finite fields, in particular multiplication of polynomials from GF(2)[X], the polynomial ring over GF(2).

The operation is also known as an XOR multiplication, as carry-discarding addition is equivalent to an exclusive or.

Given two numbers ${\displaystyle \textstyle a=\sum _{i}a_{i}2^{i}}$ and ${\displaystyle \textstyle b=\sum _{i}b_{i}2^{i}}$, with ${\displaystyle a_{i},b_{i}\in \{0,1\}}$ denoting the bits of these numbers, the carry-less product of these two numbers is defined to be ${\displaystyle \textstyle c=\sum _{i}c_{i}2^{i}}$, with each bit ${\displaystyle c_{i}}$ computed as the exclusive or of products of bits from the input numbers as follows:

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.

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

and the product of these is