Mais um blog inútil.

Depois de um breve hiato, volto a este Blol colocar pensamentos inúteis. E hoje pensei na multiplicação de polinómios - em particular, polinómios com coeficientes mod 2, i.e. [latex]\mathbb{F}_2[x][/latex]. Como é que representamos estes polinómios?

Dado que cada coeficiente apenas pode ser 0 ou 1, podemos utilizar apenas um bit para estes. Assim, se tivermos um polinómio [latex]x^3 + x + 1[/latex], representamos o mesmo por 0b1011 ou 0x0B.

A adição de polinómios é trivial - consiste unicamente em aplicar a operação XOR, dado que XOR é adição mod 2. A multiplicação pode ser efectuada como efectuamos multiplicações de inteiros, excepto que ignoramos todos os transportes (carries). Podemos então implementar uma multiplicação de polinómios como:

u32 polymul(u32 a, u32 b)
{
  u32 z = 0;
  while(b != 0)
  {
    if(b&1 != 0)
      z ^= a;
    b >>= 1; a <<= 1;
  }
  return z;
}

Isto, no entanto, contém branching e operações condicionais. Se usarmos C++, podemos criar uma função sem qualquer loop que nos permita efectuar a mesma operação:

template<u32 N> 
inline u32 mul(u32 a, u32 b)
{
  return (a & -(b&1)) ^ mul<N-1>(a<<1, b>>1);
}

template<>
inline u32 mul<0>(u32 a, u32 b)
{
  return 0;
}

O parâmetro N, utilizado na instanciação da função, corresponde ao grau máximo dos polinómios de entrada. No caso de um inteiro de 32 bits, a soma dos graus de a e b não poderá exceder 32, de forma a evitar overflows.