Optimieren arithmetische y = x * x in Galoisfeld

Question

Ich habe diesen C-Code Multiplikationen über GF zu tun (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);
}

Das ist mehr oder weniger die Text-Book-Implementierung.

Ich frage mich, ob ich dort eine clevere Optimierung für obige Algorithmus ist, wenn ich das eine behaupten kann, ist immer b, z.B. Ich anstelle der Multiplikation quadriert. Ich bin nicht nach einer kryptographischen btw Verwendung. Ich möchte nur die Tatsache zunutze machen, die x * x in GF (8) mit Null-Bits, die Bits von x verschachtelt eins nach dem anderen.

Es gibt bereits sehr clever Methoden, um die Bit-Verschachtelung zu tun, aber da ich herausgefunden habe, dass x * x in GF (8) ist das Bit, was Verschachtelung (durch Zufall) Ich kann nicht aufhören zu versuchen, es zu benutzen für Bit-Verschachtelung Optimierungen.

Irgendwelche Ideen?

Answer 1

Table-basiert? Link

Und wenn Sie sind auf x * x, es ist eine Sparse Matrix.

Hier ist ein anderes gutes Papier (und eine Bibliothek)

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

Oder wenn Sie mögen:

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

Der Grund, dass dieser Ansatz effizienter ist als über den Original-Code ist in erster Linie, weil die Schleife nur, bis all ‚interessant‘ Bits in dem Argumente verbraucht wird durchgeführt wird, im Gegensatz zu blind alle (9) Bits zu überprüfen.

Eine Tabelle basierter Ansatz allerdings schneller wird.

Answer 3

Lookup-Tabelle ist definitiv der schnellste für Polynom Basis galois Quadrierung. Es ist auch die schnellste für die Multiplikation, wenn GF (8) verwendet wird, aber die Tische bekommen zu groß für größere Felder wie in ECC verwendet. Bei der Multiplikation in größeren Feldern, ist der beste Algorithmus ist die ‚links nach rechts verbinden‘ Methode ... (siehe http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X Algorithmus 2.36, Seite 50).

Answer 4

Sie könnten wahrscheinlich einige Montage schreiben einen etwas besseren Job zu machen. Ich würde jedoch, ziemlich überrascht, wenn dies der Engpass in der Anwendung ist; haben Sie jede Profilierung getan? Diese Funktion scheint nicht, wie es lohnt zu optimieren.

Answer 5

Dies ist wahrscheinlich nicht das, was Sie suchen, aber hier ist eine kleinere Speedup:

Führen Sie nur ein Argument, wenn sie gleich sind garantiert.

Answer 6

Es könnte der Compiler ein wenig helfen zu markieren „a“ und „b“ als konst. Oder Entrollen der Schleife mit der Hand. Es wäre traurig, wenn es geholfen, obwohl ...

Ist es nicht ein Patent Minenfeld, nebenbei gesagt?