Ottimizza y = x * x nell'aritmetica del campo di Galois

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

Domanda

Ho questo codice C per fare moltiplicazioni su 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);
}

Questa è più o meno l'implementazione del libro di testo.

Mi chiedo se esiste un'ottimizzazione intelligente per l'algoritmo sopra se posso affermare che a è sempre b, ad es. Faccio la quadratura invece della moltiplicazione. Non sto cercando un uso crittografico a proposito. Voglio solo sfruttare il fatto che x * x in GF (8) interlaccia i bit di x con zero bit uno per uno.

Esistono già metodi abbastanza intelligenti per eseguire l'interleaving dei bit, ma poiché ho scoperto che x * x in GF (8) esegue l'interleaving dei bit (per caso) non riesco a smettere di provare a usarlo per ottimizzazioni bit-interleaving.

Qualche idea?

È stato utile?

Soluzione

basato su tabella? link

E quando sei limitato a x * x, è una matrice sparsa.

Ecco un altro buona carta (e una biblioteca)

Altri suggerimenti

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

O se ti piace: 

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

Il motivo per cui questo approccio è più efficiente del codice originale sopra è principalmente dovuto al fatto che il ciclo viene eseguito solo fino a quando tutti i bit "interessanti" nell'argomento non vengono consumati invece di controllare ciecamente tutti (9) bit.

Un approccio basato su una tabella sarà comunque più veloce.

La tabella di ricerca è sicuramente la più veloce per la quadratura dei galois su base polinomiale. È anche il più veloce per la moltiplicazione quando si utilizza GF (8), ma le tabelle diventano troppo grandi per campi più grandi come usato in ECC. Per la moltiplicazione in campi più grandi, l'algoritmo migliore è il metodo di combinazione da sinistra a destra ... (vedi http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X algoritmo 2.36, pagina 50).

Probabilmente potresti scrivere qualche assembly per fare un lavoro leggermente migliore. Tuttavia, sarei piuttosto sorpreso se questo fosse il collo di bottiglia nella tua applicazione; hai fatto qualche profilazione? Questa funzione non sembra valga la pena di essere ottimizzata.

Questo probabilmente non è quello che stai cercando, ma ecco un piccolo aumento di velocità:

Passa solo un argomento, se è garantito che siano gli stessi.

Potrebbe aiutare un po 'il compilatore a contrassegnare " a " e " b " come const. O srotolare il ciclo a mano. Sarebbe triste se aiutasse, però ...

Non è un campo minato di brevetti, comunque?

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top