Optimizar y = x * x em Galois aritmética campo
-
02-07-2019 - |
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?
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?