優化Y = X * X在伽羅瓦域算術

Question

我有這樣的C代碼在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); 
} 

這或多或少課本實現。

我想知道如果我能斷言a總是b，例如我是否有上述算法的巧妙優化。我做平方而不是乘法。我沒有使用密碼使用btw。我只想利用GF（8）中的x * x將x的位逐位交織爲零的事實。我已經發現GF（8）中的x * x做位交織的事情（偶然），我不能停止嘗試使用它進行比特交織優化。

任何想法？

Answer 1

基於表？ link

而當你被限制爲x * x時，它是一個稀疏矩陣。

這裏的另一個good paper (and a library)

Answer 2

你可以寫一些程序集來做一個稍微好一點的工作。但是，如果這是您應用程序的瓶頸，我會很驚訝。你有沒有做過任何分析？這個功能似乎並不值得優化。

Answer 3

這可能不是你所尋找的，但這裏有一個輕微的加速：

通行證只有一個參數，如果他們保證是相同的。

Answer 4

它可以幫助編譯了一下，以紀念 「A」 和 「B」 爲const。或者手動展開循環。如果它有幫助，這將是可悲的，但...

順便說一下，這不是專利雷區嗎？

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

或者，如果你喜歡：

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

的原因，這種方法的效率比上面的原代碼主要是因爲循環只有等到在參數所有的「有趣」位執行被消耗而不是盲目地檢查所有（9）位。

雖然基於表格的方法會更快。

Answer 6

查找表絕對是多項式基礎加羅瓦平方中最快的。當使用GF（8）時，它也是乘法運算速度最快的，但對於ECC中使用的較大字段，表格變得太大。對於較大場中的乘法，最好的算法是'從左到右合併'的方法......（見http://www.amazon.com/Elliptic-Cryptography-Springer-Professional-Computing/dp/038795273X算法2.36，第50頁）。