Optimize y = x * x dans le champ Galois arithmétique

Question

J'ai ce code C à faire multiplications sur 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); 
} 

qui est plus ou moins la mise en œuvre du texte livre.

Je me demande s'il y a une optimisation intelligente pour l'algorithme ci-dessus si je peux affirmer que a est toujours b, par ex. Je fais la quadrature au lieu de la multiplication. Je ne suis pas après une utilisation cryptographique btw. Je veux juste utiliser le fait que x * x dans GF (8) entrelace les bits de x avec zéro bits un par un.

Il y a déjà des méthodes assez intelligentes pour faire l'entrelacement des bits, mais comme j'ai découvert que x * x dans GF (8) fait l'entrelacement des bits (par accident) je ne peux pas m'empêcher de l'utiliser pour les optimisations d'entrelacement de bits.

Des idées?

Answer 1

Basé sur une table? link

Et lorsque vous êtes limité à x * x, c'est une matrice clairsemée.

Voici une autre good paper (and a library)

Answer 2

Vous pourriez probablement écrire un peu d'assemblage pour faire un meilleur travail. Cependant, je serais assez surpris si c'était le goulot d'étranglement dans votre application; avez-vous fait du profilage? Cette fonction ne semble pas devoir être optimisée.

Answer 3

Ceci est probablement pas ce que vous cherchez, mais voici un petit speedup:

Passe un seul argument, si elles sont garantis d'être le même.

Answer 4

Il pourrait aider le compilateur un peu pour marquer "a" et "b" comme const. Ou dérouler la boucle à la main. Ce serait triste si ça aidait, mais ...

N'est-ce pas un champ de mines patent, au fait?

Answer 5

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 si vous aimez:

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 raison pour laquelle cette approche est plus efficace que le code original ci-dessus est principalement parce que la boucle est effectuée uniquement jusqu'à ce que tous les bits « intéressants » dans l'argument sont consommés plutôt que de vérifier aveuglément tous les (9) bits.

Une approche basée sur une table sera cependant plus rapide.

Answer 6

La table de consultation est certainement la plus rapide pour le quadrillage galois à base polynomiale. C'est aussi le plus rapide pour la multiplication en utilisant GF (8), mais les tables deviennent trop grandes pour les champs plus grands utilisés dans ECC. Pour la multiplication dans des champs plus grands, le meilleur algorithme est la méthode "de gauche à droite" ... (voir http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X algorithme 2.36, page 50).