Carryless

Carryless is a term used in mathematics and computer science to describe arithmetic operations that do not involve carries between digit positions. In base-2, carryless addition is the bitwise XOR of corresponding bits, and in many contexts carryless operations model addition and multiplication over the two-element field GF(2) or over polynomial rings GF(2)[x].

Carryless addition: For binary numbers a and b, a ⊕ b is computed by applying XOR to each bit, with no carry between positions. For example, 5 (0101) carryless-added to 3 (0011) yields 6 (0110). In this system, subtraction coincides with addition, since coefficients are taken modulo 2.

Carryless multiplication: Multiplication is performed as polynomial multiplication over GF(2), where binary digits are treated as coefficients of polynomials. The product is formed by summing shifted copies with XOR as the addition—there are no carries. The result can have a higher degree than the operands. Carryless multiplication serves as a building block for various polynomial arithmetic schemes used in error detection and cryptography.

Applications: Carryless arithmetic is used in hardware and software implementations of fast polynomial arithmetic, notably via carry-less multiply (CLMUL) instructions in modern CPUs. These operations underpin efficient computations for CRCs, Reed-Solomon codes, and cryptographic schemes that rely on arithmetic in GF(2^n) through polynomial representations.

See also: XOR, GF(2), polynomial arithmetic, CLMUL, CRC, Reed-Solomon.