* A Galois Field is a mathematical structure where addition and multiplication have been redefined so that some very useful properties are retained. Galois Fields can exist with any prime number or an "extension field" where that prime-number is vectorized. In this case, the GF2 field (prime number 2) has been extended to 8-bits (aka: a GF(2^8), aka 8-bit Galois Field).
* "Addition"'s new definition is simply XOR.
* "Multiply"'s new definition is bitshift and then add. (ie: 0b10101010 x 0b00010010 == bitshift(x, 4) + bitshift(x, 1), because the 4th and 1st bits are set to 1). And remember that "addition" has been redefined to XOR in this math, so that + means XOR.
* An Affine Transformation is A * x + B, where x is the original value. As a "Galois Field Affine Transformation", A * x and + B are all done in "Galois Field" terms.
* This is an AVX512 instruction, meaning there are 32-parallel versions of this 8-bit computation happening in parallel across a 512-bit vector.
Note: operation traditionally happens modulo a particular GF(number) to create a field. The above operations are "primitives" that can eventually create a field, but aren't making a field just yet.
Perhaps the more accurate names for these operations is "GF-addition" and "GF-pseudo-multiplication". In any case, multiplication is any combination of the 8-bitshifts (bitshift0, bitshift1, bitshift2...) and the 8x such results added together (depending on the 1 or 0 on that bit). Meaning you can very easily describe bitshift-and-xor operations to other cryptographers who are operating in "GF-language".
Its actually really easy, though the terminology is a pain in the ass.
----------
Traditionally, this multiplication on Intel has been called "carryless multiplication" (clmul) and "polynomial multiplication" (pmull) on ARM. I preferred these names personally.
But if Intel wants to call this the "gfp8affineqb", then so be it, they're the ones naming this instruction not me. Its... a reasonable name, I feel like a better name exists out there but I can't think of one. But its certainly not a perfect name IMO. Maybe "clp8affineqb" ("carryless 8-bit affine") would be my preference?
How do you achieve actual multiplication? I remember there was some polynomial that you had to divide by, and then every non-zero element becomes invertible? Such pseudo-multiplication doesn't seem to be invertible, as 0b00000010 multiplied by anything will always end with a 0: 0b???????0.
For anyone else who was also seeing just garbled characters in the title, and since the first few paragraphs of the linked article don't explain what that is:
GF2P8AFFINEQB is one of the AVX-512 CPU instructions that performs an affine transformation (essentially AX+b) on a Galois field - finite number fields used in coding theory and cryptography.
Thanks for the link. We were previously using GFNI for bit reversal and 8-bit shifts, and I just extended that to our 8-bit BroadcastSignBit (https://github.com/google/highway/pull/1784).
[+] [-] dragontamer|2 years ago|reply
* A Galois Field is a mathematical structure where addition and multiplication have been redefined so that some very useful properties are retained. Galois Fields can exist with any prime number or an "extension field" where that prime-number is vectorized. In this case, the GF2 field (prime number 2) has been extended to 8-bits (aka: a GF(2^8), aka 8-bit Galois Field).
* "Addition"'s new definition is simply XOR.
* "Multiply"'s new definition is bitshift and then add. (ie: 0b10101010 x 0b00010010 == bitshift(x, 4) + bitshift(x, 1), because the 4th and 1st bits are set to 1). And remember that "addition" has been redefined to XOR in this math, so that + means XOR.
* An Affine Transformation is A * x + B, where x is the original value. As a "Galois Field Affine Transformation", A * x and + B are all done in "Galois Field" terms.
* This is an AVX512 instruction, meaning there are 32-parallel versions of this 8-bit computation happening in parallel across a 512-bit vector.
Note: operation traditionally happens modulo a particular GF(number) to create a field. The above operations are "primitives" that can eventually create a field, but aren't making a field just yet.
Perhaps the more accurate names for these operations is "GF-addition" and "GF-pseudo-multiplication". In any case, multiplication is any combination of the 8-bitshifts (bitshift0, bitshift1, bitshift2...) and the 8x such results added together (depending on the 1 or 0 on that bit). Meaning you can very easily describe bitshift-and-xor operations to other cryptographers who are operating in "GF-language".
Its actually really easy, though the terminology is a pain in the ass.
----------
Traditionally, this multiplication on Intel has been called "carryless multiplication" (clmul) and "polynomial multiplication" (pmull) on ARM. I preferred these names personally.
But if Intel wants to call this the "gfp8affineqb", then so be it, they're the ones naming this instruction not me. Its... a reasonable name, I feel like a better name exists out there but I can't think of one. But its certainly not a perfect name IMO. Maybe "clp8affineqb" ("carryless 8-bit affine") would be my preference?
[+] [-] H8crilA|2 years ago|reply
[+] [-] gpderetta|2 years ago|reply
[+] [-] zodzedzi|2 years ago|reply
GF2P8AFFINEQB is one of the AVX-512 CPU instructions that performs an affine transformation (essentially AX+b) on a Galois field - finite number fields used in coding theory and cryptography.
https://en.wikipedia.org/wiki/AVX-512#GFNI
[+] [-] spicymaki|2 years ago|reply
[+] [-] phiiiillll|2 years ago|reply
https://gist.github.com/animetosho/d3ca95da2131b5813e16b5bb1...
[+] [-] janwas|2 years ago|reply
[+] [-] stabbles|2 years ago|reply
[+] [-] ur-whale|2 years ago|reply
https://www.felixcloutier.com/x86/gf2p8affineqb
https://gist.github.com/animetosho/d3ca95da2131b5813e16b5bb1...