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.
Applications[edit]
The elements of GF(2n), 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.
Implementations[edit]
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.
Other bases[edit]
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.