pclmulqdq Tricks – Wunk

[utterances-bot]

pclmulqdq Tricks – Wunk

https://wunkolo.github.io/post/2020/05/pclmulqdq-tricks/

[genos]

Interesting post, thanks!

Sorry to be that guy, but one nitpick: you've described multiplying polynomials in Z_2[x], not GF(2^n), since you don't reduce your polynomials modulo some irreducible reducing polynomial; c.f. Wikipedia.

[someferge]

Thank you Joey - do you have examples in C99/C# on how to compute the inverse of a carryless mulitplication?

[Marc-B-Reynolds]

@someferge A little late but it's a special case of exponentiation. For 64-bit the maximum period is 64 (and all other periods are powers-of-two) so x^(-1) = x^(63).

uint64_t cl_mul_inv_64(uint64_t x)
{
  uint64_t r = x;

  for(uint32_t i=0; i<5; i++) {
    x = cl_mul_64(x,x);    // this can be a bit-scatter to even
    r = cl_mul_64(r,x);
  }
  return r;
}