Optimice y = x*x en la aritmética de campos de Galois

Question

Tengo este código C para hacer multiplicaciones sobre GF(8):

int32_t GaloisMultiply (int32_t a, int32_t b) 
{
    int32_t i;
    int32_t mask = 0x100;
    int32_t y = 0;

    for(i=0;i<8;i++) 
    {
        if(b & mask) 
        {
            y ^= a;
        }
        mask >>= 1;
        y <<= 1;
    }

    if(b & 0x1) 
    {
        y ^= a;
    }

    return(y);
}

Esa es más o menos la implementación de los libros de texto.

Me pregunto si existe una optimización inteligente para el algoritmo anterior si puedo afirmar que a es siempre b, p.Hago cuadrados en lugar de multiplicaciones.Por cierto, no busco un uso criptográfico.Sólo quiero aprovechar el hecho de que x*x en GF(8) intercala los bits de x con cero bits uno por uno.

Ya existen métodos bastante inteligentes para realizar el entrelazado de bits, pero desde que descubrí que x*x en GF(8) realiza el entrelazado de bits (por accidente), no puedo dejar de intentar usarlo para el entrelazado de bits. optimizaciones.

¿Algunas ideas?

Answer 1

¿Basado en tablas? enlace

Y cuando estás limitado a x*x, es una matriz escasa.

Aquí está otro buen papel (y una biblioteca)

Answer 2

int32_t GaloisMultiply( int32_t a ) 
{
  int32_t y = 0;
  int32_t b = a & 0x01ff;

  while ( b ) 
  {
    if ( b & 1 ) 
      y ^= a;

    a <<= 1;
    b >>= 1;
  }
  return y;
}

O si quieres:

int32_t GaloisMultiply( int32_t a ) 
{
  int32_t y = 0;
  for ( int32_t b = a & 0x01ff; b; b >>= 1 )
  {
    if ( b & 1 ) 
      y ^= a;

    a <<= 1;
  }
  return y;
}

La razón por la que este enfoque es más eficiente que el código original anterior es principalmente porque el bucle solo se realiza hasta que se consumen todos los bits "interesantes" del argumento, en lugar de verificar ciegamente todos los (9) bits.

Sin embargo, un enfoque basado en tablas será más rápido.

Answer 3

La tabla de búsqueda es definitivamente la más rápida para la elevación al cuadrado de Galois en base polinómica.También es el más rápido para la multiplicación cuando se usa GF(8), pero las tablas se vuelven demasiado grandes para campos más grandes como los que se usan en ECC.Para la multiplicación en campos más grandes, el mejor algoritmo es el método de 'combinación de izquierda a derecha'...(ver http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X algoritmo 2.36, página 50).

Answer 4

Probablemente podrías escribir algún ensamblaje para hacer un trabajo un poco mejor.Sin embargo, me sorprendería mucho que este fuera el cuello de botella de su aplicación;¿Has hecho algún perfil?No parece que valga la pena optimizar esta función.

Answer 5

Probablemente esto no sea lo que estás buscando, pero aquí tienes una pequeña aceleración:

Pase solo un argumento, si se garantiza que serán iguales.

Answer 6

Podría ayudar un poco al compilador marcar "a" y "b" como constantes.O desenrollar el lazo a mano.Aunque sería triste si ayudara...

Por cierto, ¿no es un campo minado de patentes?