Optimiser y = x * x en arithmétique de corps de Galois

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

Question

J'ai ce code C pour faire des 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);
}

C'est plus ou moins la mise en œuvre du manuel.

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

Il existe déjà des méthodes assez astucieuses pour effectuer l'entrelacement de bits, mais depuis que j'ai découvert que x * x dans GF (8) effectue l'entrelacement de bits (par accident), je ne peux pas arrêter d'essayer de l'utiliser optimisations d'entrelacement de bits.

Des idées?

Était-ce utile?

La solution

Basé sur une table? lien

Et quand vous êtes limité à x * x, c'est une matrice creuse.

Voici un autre bon article (et une bibliothèque)

Autres conseils

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 d'origine ci-dessus est principalement due au fait que la boucle est exécutée uniquement jusqu'à ce que tous les bits "intéressants" de l'argument soient consommés, par opposition à une vérification aveugle de tous les (9) bits.

Une approche basée sur les tables sera plus rapide cependant.

La table de correspondance est certainement la plus rapide pour la quadrature polynomiale de Galois. C'est également le plus rapide pour la multiplication lorsque vous utilisez GF (8), mais les tables deviennent trop volumineuses pour les champs plus volumineux 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).

Vous pourriez probablement écrire un assemblage pour faire un travail légèrement meilleur. Cependant, je serais assez surpris que ce soit le goulot d'étranglement dans votre application; avez-vous fait du profilage? Cette fonction ne semble pas mériter d’être optimisée.

Ce n'est probablement pas ce que vous recherchez, mais voici une accélération mineure:

Ne transmettez qu'un seul argument, s'il est garanti qu'ils sont identiques.

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

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

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top