Optimizar y = x * x em Galois aritmética campo

StackOverflow https://stackoverflow.com/questions/117352

Pergunta

Eu tenho esse código C para fazer multiplicações 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);
}

Isso é mais ou menos a implementação livro-texto.

Gostaria de saber se eu há uma otimização inteligente para algoritmo acima se eu posso afirmar que um é sempre b, por exemplo, Eu quadratura em vez de multiplicação. Eu não sou após um uso de criptografia btw. Eu só quero fazer uso do fato de que x * x em GF (8) intercala os bits de x com bits zero, um por um.

Já existem métodos bastante inteligentes para fazer o bit de intercalação, mas desde que eu descobri que x * x em GF (8) faz a coisa pouco intercalação (por acidente) eu não posso parar de tentar usá-lo para otimizações de intercalação de bit.

Todas as idéias?

Foi útil?

Solução

Table-based? ligação

E quando você está limitado a x * x, é uma matriz esparsa.

Aqui está outra papel bom (e uma biblioteca)

Outras dicas

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;
}

Ou se você gosta: 

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;
}

A razão que esta abordagem é mais eficiente do que o código original acima ocorre principalmente porque o loop só é realizada até que todos os bits 'interessante' no argumento são consumidos em oposição à verificação cegamente Todos (9) bits.

Uma abordagem tabela com base vai ser mais rápido embora.

tabela de pesquisa é definitivamente o mais rápido para o polinômio quadratura base Galois. Ele também é o mais rápido para a multiplicação ao usar GF (8), mas as mesas ficar muito grande para campos maiores como usado no ECC. Para a multiplicação em campos maiores, o melhor algoritmo é a 'esquerda para a direita combinar' método ... (ver http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X algoritmo 2.36, página 50).

Você provavelmente poderia escrever algum conjunto para fazer um trabalho um pouco melhor. No entanto, eu ficaria muito surpreso se isso era o gargalo na sua aplicação; Você já fez alguma profiling? Esta função não parece que vale a pena otimização.

Isto não é provavelmente o que você está procurando, mas aqui está um menor aumento de velocidade:

Passe apenas um argumento, se eles são garantidos para ser o mesmo.

Pode ajudar o compilador um pouco a marca "a" e "b" como const. Ou desenrolar o loop com a mão. Seria triste se ajudou, embora ...

Não é um campo minado de patentes, pelo caminho?

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top