CLMUL instruction set

{{Short description|Extension to the x86 instruction set}}

Carry-less Multiplication (CLMUL) is an extension to the x86 instruction set used by microprocessors from Intel and AMD which was proposed by Intel in March 2008{{cite web | url=http://softwareprojects.intel.com/avx/ | title=Intel Software Network | publisher=Intel | accessdate=2008-04-05 | url-status=dead | archiveurl=https://web.archive.org/web/20080407095317/http://softwareprojects.intel.com/avx/ | archivedate=2008-04-07 }} and made available in the Intel Westmere processors announced in early 2010. Mathematically, the instruction implements multiplication of polynomials over the finite field GF(2) where the bitstring $a\_0a\_1\backslash ldots\; a\_\{63\}$ represents the polynomial $a\_0\; +\; a\_1X\; +\; a\_2X^2\; +\; \backslash cdots\; +\; a\_\{63\}X^\{63\}$. The CLMUL instruction also allows a more efficient implementation of the closely related multiplication of larger finite fields GF(2^k) than the traditional instruction set.{{cite web

|url=http://software.intel.com/en-us/articles/intel-carry-less-multiplication-instruction-and-its-usage-for-computing-the-gcm-mode/

|archive-url=https://web.archive.org/web/20190806061845/https://software.intel.com/sites/default/files/managed/72/cc/clmul-wp-rev-2.02-2014-04-20.pdf

|title=Intel Carry-Less Multiplication Instruction and its Usage for Computing the GCM Mode – Rev 2.02

|publisher=Intel|author1=Shay Gueron|author2=Michael E. Kounavis|date=2014-04-20|archive-date=2019-08-06}}

One use of these instructions is to improve the speed of applications doing block cipher encryption in Galois/Counter Mode, which depends on finite field GF(2^k) multiplication. Another application is the fast calculation of CRC values,{{cite web|url=http://www.intel.com/content/dam/www/public/us/en/documents/white-papers/fast-crc-computation-generic-polynomials-pclmulqdq-paper.pdf|title=Fast CRC Computation for Generic Polynomials Using PCLMULQDQ}} including those used to implement the LZ77 sliding window DEFLATE algorithm in zlib and pngcrush.{{cite web|url=https://blog.cloudflare.com/cloudflare-fights-cancer/|title=Fighting Cancer: The Unexpected Benefit Of Open Sourcing Our Code|author=Vlad Krasnov|publisher=CloudFlare|date=2015-07-08|accessdate=2016-09-04}}

ARMv8 also has a version of CLMUL. SPARC calls their version XMULX, for "XOR multiplication".